الگوریتم مرتب سازی سریع (Quick Sort)

[Sarp]

قبل از شروع هرگونه توضیحی به دقت به تصویر زیر توجه نمایید و خودتان سعی کنید تا با توجه به این مثال به درکی هرچند مختصر نسبت به این الگوریتم، دست یابید.

​

quick sort چیست ؟
یکی از سریع ترین الگوریتم های مرتب سازی، الگوریتم quick sort می باشد که نه تنها در بحث آموزش بلکه در محیط ها و برنامه های کاربردی روزمره نیز مورد استفاده قرار می گیرد. پیچیدگی این الگوریتم در حالت میانگین ( O(n log n و در بدترین حالت ( O(n2 می باشد. این الگوریتم مرتب سازی توسط فردی به نام هور «1962» ابداع گردید. این الگوریتم مشابه الگوریتم مرتب سازی ادغامی، از روش تقسیم و حل یا divide-and-conquer strategy حل می گردد.

روش حل الگوریتم:
در این روش ابتدا آرایه را به دو قسمت تقسیم نموده و بعد یکی از عناصر آرایه را به عنوان محور اصلی در نظر می گیریم. «فرقی نمی کند که عنصر اولی باشد یا دومی یا وسطی و یا هر عنصر دیگر». سپس تمام عناصر کوچکتر از عنصر محور را در سمت چپ و عناصر بزرگتر را در سمت راست عنصر محور قرار می دهیم. حال نتیجه کار به صورت دو آرایه + عنصر محوری تبدیل شده است. اگر دقت کنید عناصر موجود در هر آرایه یا از عنصر محوری بزرگتر و یا کوچکتر می باشند ولی هیچ یک از دو آرایه مرتب نمی باشند.
پس باید دوباره به ازای هر یک از آرایه های حاصل و بصورت بازگشتی، الگوریتم فوق را اجرا نموده تا در نهایت آرایه اولیه مرتب گردد.

بررسی یک مثال:
برای درک بهتر این الگوریتم به تصویر فوق مجددا نگاه کنید. آرایه ای که قرار است با استفاده از این الگوریتم مرتب گردد شامل مقادیر زیر می باشد.
1, 12, 5, 26, 7, 14, 3, 7, 2
برای شروع یکی از اعضا «بطور مثال عدد 7» را به عنوان عنصر محوری در نظر می گیریم. حال دو متغیر i و j را در نظر گرفته که اولی به ابتدای آرایه و دومی به انتها آرایه اشاره می کنند. به کمک این دو متغیر و تا زمانی که i>j نشده است، یکی یکی عناصر را به عنصر محوری مقایسه می کنیم و در جای خود قرار می دهیم. سپس یکی به i اضافه نموده و یک واحد نیز از j کم می نماییم. نتیجه کار بصورت زیر می گردد:

1,2,5,7,3 14,7,26,12​

در این حالت فرض می کنیم که دو آرایه برای مرتب کردن داریم و دوباره همین عملیات را برای هریک از آرایه ها انجام می دهیم تا در نهایت به جواب زیر دست یابیم.

1,2,3,5,7,7,12,14,26​

در ادامه نمونه برنامه ای که الگوریتم فوق را پیاده سازی کرده است، نمایش داده می شود. در این برنامه ده عدد بصورت تصادفی ایجاد شده و سپس مرتب می گردند. نکته مهم دیگر در این مثال آن است که مدت زمان انجام این عملیات نیز محاسبه شده و به عنوان خروجی بازگردانده می شود. برای اینکه زمان دقیق انجام این محاسبه بدست آید، زمان بصورت میلی ثانیه در نظر گرفته شده است.

public class QuickSort {
   private static long comparisons = 0;
   private static long exchanges = 0;
		
   public static void quicksort(double[] a) {
       shuffle(a); // to guard against worst-case
       quicksort(a, 0, a.length - 1);
   }
		
		// quicksort a[left] to a[right]
  public static void quicksort(double[] a, int left, int right) {
    if (right <= left) return;
    int i = partition(a, left, right);
    quicksort(a, left, i-1);
    quicksort(a, i+1, right);
  }
		
		// partition a[left] to a[right], assumes left < right
  private static int partition(double[] a, int left, int right) {
    int i = left - 1;
    int j = right;
    while (true) {
        while (less(a[++i], a[right])); //  		find item on left to swap
                                                          		// a[right] acts as sentinel
        while (less(a[right], a[--j])) //  		find item on right to swap
            if (j ==  		left) break; // don't go out-of-bounds
        if (i >= j) break; // check if  		pointers cross
        exch(a, i, j); // swap two elements  		into place
    }
    exch(a, i, right); // swap with partition element
    return i;
		}
		
		// is x < y ?
		private static boolean less(double x, double y) {
    comparisons++;
    return (x < y);
		}
		
		// exchange a[i] and a[j]
		private static void exch(double[] a, int i, int j) {
    exchanges++;
    double swap = a[i];
    a[i] = a[j];
    a[j] = swap;
		}
		
		// shuffle the array a[]
    private static void shuffle(double[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int r = i + (int) (Math.random() *  		(N-i)); // between i and N-1
        exch(a, i, r);
    }
		}
		
		// test client
		public static void main(String[] args) {
		// generate 10 random real numbers between 0 and 1
     long start = System.currentTimeMillis();
     double[] a = new double[10];
    for (int i = 0; i < 10; i++)
        a[i] = Math.random();
    long stop = System.currentTimeMillis();
    double elapsed = (stop - start) / 1000.0;
    System.out.println("Generating input: " + elapsed + "  		seconds");
		
		// sort them
  System.out.print(" primaray array is: \n");
  for(int k=0; k<10; k++){
    System.out.print(a[k]);
    if (k<9) 
        System.out.print(" , ");
  }
    System.out.print("\n");
    start = System.currentTimeMillis();
    quicksort(a);
    stop = System.currentTimeMillis();
    System.out.print(" sorted array is: \n ");
  for(int k=0; k<10; k++){
    System.out.print(a[k]);
    if (k<9)
        System.out.print(" , ");
  }
    System.out.print("\n");
    System.out.print("Start sort time (in mili second) is: " +  		start +"\n");
    System.out.print("end sort time (in mili second) is: " + stop  		+"\n");
    elapsed = (stop - start) / 1000.0;
    System.out.println("Quicksort: " + elapsed + " seconds");
		
		// print statistics
    System.out.println("Comparisons: " + comparisons);
    System.out.println("Exchanges: " + exchanges);
  }
		}