الگوریتم مرتب سازی سریع یا Quick-sort
مرتب سازی سریع یکی از بهترین الگوریتم های مرتب سازی است است که سرعت بسیار مناسبی دارد. در دو پست قبل مفهوم مرتب سازی و مرتب سازی حبابی (Bubble sort) را بررسی کردیم. امروز می خواهیم به مرتب سازی سریع (Quick sort ) بپردازیم.
با ما در اوپن مایند همراه باشید.
فهرست مطالب
مرور الگوریتم های قبلی
قبل از این که به ادامه بحث بپردازیم یک مرور بکنیم از سایر الگوریتم ها که در روز های آینده آن ها را بررسی خواهیم کرد:
- مفهوم مرتب سازی
- Bubble sort
- Insertion sort
- Selection Sort
- Merge sort
- Quick sort
- Heap sort
- Distribution sorts
- Concurrent sorts
- Counting Sort
مرتب سازی سریع
مرتب سازی سریع یکی از بهترین الگوریتم های مرتب سازی است است که سرعت بسیار مناسبی دارد و اگر درست پیاده سازی شود یکی از سریع ترین الگوریتم ها خواهد بود . Quick sort یک روش مرتب سازی بازگشتی است، البته ممکن است این سوال برای شما پیش بیاید اگر بازگشتی است پس چرا می گوییم از لحاظ حافظه و سرعت خوب است دلیلش این است که این الگوریتم دقیقا فیتِ کش است .
پیاده سازی الگوریتم مرتب سازی سریع
هسته quick sort تابع partition است. به همین دلیل ابتدا با بررسی پیاده سازی این تابع شروع می کنیم.
تابع partition
کد تابع partition در زیر آمده است.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | // partition function int partition(int A[], int p, int q) { int temp; int x = A[p]; int i = p; for (int j = p + 1; j <= q; j++) { if (A[j] <= x) { i++; temp = A[j]; A[j] = A[i]; A[i] = temp; } } temp = A[i]; A[i] = A[p]; A[p] = temp; return i; } // |
این تابع عنصر اول بازه ای را که قرار است رویش عمل کند را در نظر می گیرد و بعد این تابع عنصر ها رو به ۲ دسته تقسیم می کند آن هایی که بزرگ تر از عنصر اول هستند و آن هایی که کوچک تر از عنصر اول هستند و عنصر اول را بین این دو دسته قرار می دهد و بعد مکانی را که عنصر ما بین این دو دسته قرار دارد را بر می گرداند . اول کد بالا را خوب نگاه کنید و بعد عکس های زیر را ببینید تا تابع partition را بهتر درک کنید :
تابع مرتب سازی سریع Quick sort
حالا می رویم سراغ خود تابع مرتب سازی سریع یا Quick sort که از تابع partition استفاده می کند.
1 2 3 4 5 6 7 8 9 10 11 12 | // quick sort void Quick_sort(int A[], int p, int r) { int q; if (p < r) { q = partition(A, p, r); Quick_sort(A, p, q - 1); Quick_sort(A, q + 1, r); } } // |
همین طور که می بینید quick sort یک الگوریتم بازگشتی است که مرتب partition و خود را را فرا می خواند این کار را می کند تا زمانی که آرایه هایی به طول یک به دست آید و آرایه به طول یک خود مرتب است و اینگونه است که با استفاده از روش تقسیم و حل می توانیم آرایه را سورت کنیم.
کد نهایی
در کد زیر تابع پارتیشن (تقسیم) و مرتب سازی سریع به همراه یک تست در Main آمده است :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | // quick sort.cpp : open-mind.ir // farhad dalirani // #include "stdafx.h" #include <iostream> using namespace std; // partition function int partition(int A[], int p, int q) { int temp; int x = A[p]; int i = p; for (int j = p + 1; j <= q; j++) { if (A[j] <= x) { i++; temp = A[j]; A[j] = A[i]; A[i] = temp; } } temp = A[i]; A[i] = A[p]; A[p] = temp; return i; } // // quick sort void Quick_sort(int A[], int p, int r) { int q; if (p < r) { q = partition(A, p, r); Quick_sort(A, p, q - 1); Quick_sort(A, q + 1, r); } } // int main() { // one example int i; int A[9] = { 9, 5, 7, 3, 2, 1, 4, 6, 0 }; // print array before sort for (int i = 0; i < 9; i++) { cout << A[i] << " "; } cout << endl; // Quick_sort(A, 0, 8); // print array after sort for (int i = 0; i < 9; i++) { cout << A[i] << " "; } cout << endl; // return 0; } |
کد کلاس مرتب سازی سریع (Quick sort) به زبان جاوا:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | public class Quicksort { private int[] numbers; private int number; public void sort(int[] values) { // check for empty or null array if (values ==null || values.length==0){ return; } this.numbers = values; number = values.length; quicksort(0, number - 1); } private void quicksort(int low, int high) { int i = low, j = high; // Get the pivot element from the middle of the list int pivot = numbers[low + (high-low)/2]; // Divide into two lists while (i <= j) { // If the current value from the left list is smaller than the pivot // element then get the next element from the left list while (numbers[i] < pivot) { i++; } // If the current value from the right list is larger than the pivot // element then get the next element from the right list while (numbers[j] > pivot) { j--; } // If we have found a value in the left list which is larger than // the pivot element and if we have found a value in the right list // which is smaller than the pivot element then we exchange the // values. // As we are done we can increase i and j if (i <= j) { exchange(i, j); i++; j--; } } // Recursion if (low < j) quicksort(low, j); if (i < high) quicksort(i, high); } private void exchange(int i, int j) { int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; } } |
سلام من چه کدی باید به این برنامه اضافه کنم تا بتونم تعداد دقیق دفعات جابه جایی داده هارو مقایسه کنم؟
سلام. چطور میتونم قسمت پارتیشن و کوییک سورت رو در یک تابع بازگشتی بنویسم؟!
سلام.
می تونید در محل فراخوانی تابع partition (در تابع Quick_sort) ، بدنه تعریف اون رو بذارید و به جای دستور
به سادگی مقدار i رو به q انتساب بدید.
موفق باشید
سلام چجوری میتونم مرتب سازی سریع رو به زبان پایتون براتون بفرستم؟
سلام ، به برگه تماس با ما (+) مراجعه کنید.
واقعا ممنونم خیلی خوب بود
سلام ،
استفاده کردیم ….
از زحمات شما مچکرم.
سلام خسته نباشید
میخواستم بدونم ک کدام یک از مرتب سازیهای مبتنی بر مقایسه در بهترین حالت، دارای مرتبه زمانی بهتری است؟
ممنون میشم پاسخ بدین
http://open-mind.ir/?p=1247#comment-3008
در حالت متوسط Quick-sort، با داشتن درجه زمانی ((O(nlg(n و سربار حافظه بسیار کم، سریع ترین عملکرد را دارد.
البته برای جلوگیری از به وجود آمدن درجه زمانی (O(n^2 در Quick-sort در بدترین حالت، Quick-sort با روش میانه سه، پیاده سازی می شود.
روش میانه سه چه روشیه میشه لطفا بگید
سلام
اینجا آموزش شده داده (روی لینک کلیک کنید) :
روش بهینه سازی مرتب سازی سریع با میانه سه
سلام
اگه در مرتب سازی سریع بجای انتخاب عنصر اول بعنوان عنصر محوری ، عنصر وسط بعنوان عنصر محوری انتخاب شود الگوریتم آن به چه صورت خواهد بود؟
ممنون میشم جوابشو به ایمیلم ارسال کنید
از لحاظ آماری و با توجه امید ریاضی محاسبه شده برای مرتب سازی سریع، تفاوتی ایجاد نمیشه
سلام خیلی سایت خوبی دارید واقعا کداتون خیلی خوب و کاربردی هست
مرتب سازی ادغامی راهم اگر دارید بذارید ممنون میشم
تشکر ، تا چند روز آینده حتما می گذارم.
سلام میشه برام سورس کد الگوریتم quick sort به زبان ++c را ایمیل بکنید ممنون از همکاری شما و تلاش برای بهتر شدن معلومات آموزشی ما….
خب اینی که اینجاست کد کوییک سورت است!
سلام میشه لطف کنید کد radix sortبرای اعداد ۳۲ بیتی برام ایمیل کنید ممنون
ایمیل کردم
سلام میشه لطف کنید کد radix sortبرای اعداد ۳۲ بیتی رو برام ایمیل کنید ممنون میشم
ایمیل کردم
میشه واسه منم ایمیل کنید…خیییییییییییییلی نیاز دارم واسه فردا توضیحشو نمی دونم 🙁
سلام
میخواستم الگوریتم در روش مرتب سازی به غیر از حبابی همراه با توضیح و کدشون برام ایمیل کنید
تو سایت چند الگوریتم دیگه با توضیحات هست می تونید از آن ها استفاده کنید.
با سلام
ببخشید اگر بخوام radix sort رو برای اعداد ۳۲ بیتی بنویسم چیکار کنم؟میشه برام ایمیل کنید ممنون
ایمیلتون رو چک کنید.
سلام آقای دلیرانی ببخشید امروز که امتحان الگوریتم ها بود من یه مشکلی برام پیش اومد نتونستم به امتحان برسم،واقعانم خونده بودم و خودتون امید
نید نمره اش چقد مهمه،ازتون خواهش میکنم یکاری بکنید،اگه میشه دوباره ازم امتحان بگیرید،اصلا امکانش هست؟؟؟
ممنون میشم اگه جواب بدید
باید با دکتر صحبت کنم ، سه شنبه جواب را بعد از کلاس می گویم.
ممنون