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);
}
}