merge sort

السلام عليكم

راجع ال insertion sort

شرح سريع و مبسط لل merge sort :::

عندما يكون لدينا قائمة list بها بعض العناصر و نريد ترتيب هذا العناصر عن طريق ال merge sort

اولا نقوم بتقسيم ال list التى لدينا الى نصفين متساويين اذا كان عدد العناصر زوجى اما اذا كان عدد العناصر فردى نقوم بتقسيمها الى جزئين بحيث ان يكون الجزء على الطرف اليمين يزيد عن الجزء على الطرف الايسر بمقدار واحد يعنى لو كان عدد العناصر سبعة

نقسمها الى 4 و 3

بعد هذه الخطوة يصبح لدينا two list قائمتين من العناصر

انت تقوم بالتعامل مع كل قائمة على حدا.....

و تقوم بتقسيم القائمة اليمنى مثلا الى قائمتين و القائمتين تقوم بتقسيمهم الى اخرتين و هكذا

و نفس الخطوات مع القائمة اليسرى

الى ان نجد ان كل عنصر اصبح بقائمة منفصلة..اى قمنا بتفتيت العناصر و اصبح كل عنصر مستقل

الصورة تحكى::::::..................

و بعد ان توصلنا الى هذه المرحلة نقوم بترتيب العناصر و دمجهم مع بعضهم البعض حتى نجمعهم مرة اخرى فى list واحدة

لاحظ الصورة...سترى عملية المقارنة و دمج العناصر

الان مع الكود::::::

يطلب من المستخدم ادخال 6 عناصر اولا ثم يقوم بعرضها قبل الترتيب و عرضها بعد الترتيب

و نجد ان هناك داله خاصة بترتيب العناصر تسمى merge_Sort

import java.util.Scanner;

public class mergeSort{
  static int array[]=new int [6];
  public static void main(String a[]){
    int i;
    Scanner input=new Scanner(System.in);
    System.out.println("please,insert 6 numbers to be sorted:");
    for(i=0;i<6;i++){
   	array=input.nextInt(); 
    }
    System.out.println("Values Before the sort:\n");
    for(i = 0; i < array.length; i++)
      System.out.print( array+"  ");
    System.out.println();
    merge_Sort(array,0, array.length-1);
    System.out.print("Values after the sort:\n");
    for(i = 0; i <array.length; i++)
      System.out.print(array+"  ");
    System.out.println();
    System.out.println("PAUSE");
  }

  public static void merge_Sort(int array[],int lo, int n){
    int low = lo;
    int high = n;
    if (low >= high) {
      return;
    }

    int middle = (low + high) / 2;
    merge_Sort(array, low, middle);
    merge_Sort(array, middle + 1, high);
    int end_low = middle;
    int start_high = middle + 1;
    while ((lo <= end_low) && (start_high <= high)) {
      if (array[low] < array[start_high]) {
        low++;
            } else {
        int Temp = array[start_high];
        for (int k = start_high- 1; k >= low; k--) {
          array[k+1] = array[k];
        }
                array[low] = Temp;
                low++;
                end_low++;
                start_high++;
            }
        }
    }
}

نجد فى هذه الدالة merge_Sort هذه المتغيرات low و high حيث ان

المتغير low يشير الى بداية القائمة من الناحية اليسرى

و المتغير high يشير الى منتصف القائمة اى من بداية اللون الاحمر كما هو فى الصورة السابقة

و نقوم فى هذه الدالة بتقسيم القائمة

و ترتيب العناصر

بالنسبة للصور::انا عملتها على الاوفيس معذرة على عدم وضوحها جيدا