الگوریتم های مرتب سازی : بهینه سازی Quick-sort با میانه سه
در این مطلب از وب سایت اوپن مایند می خواهیم کمی بیشتر از Quick-sort صحبت کنیم. اگر از Quick-sort چیزی نمی دانید ابتدا این مطلب را بخوانید.
در الگوریتم Quick-sort، بدترین حالت (با درجه زمانی (O(n^2 ) برای ما دردسرساز می شود و بهترین حالت (با درجه زمانی ((O(n*lg(n )، بهترین زمان اجرا را دارد! در شکل زیر بدترین حالت نشان داده شده است و آن به این صورت است که راست ترین عنصر به عنوان عنصر شاخص انتخاب می شود و همچنین آرایه از قبل به صورت صعودی مرتب شده است. به صورت کلی اگر عنصر شاخص چپ ترین یا راست ترین عنصر انتخاب شود و آرایه از قبل مرتب (چه صعودی چه نزولی) باشد، الگوریتم Quick-sort بدترین زمان اجرای خود را تقدیم شما خواهد کرد! البته منظور من Quick-sort به روش پیاده سازی استاندارد و متداول است.
برای جلوگیری از ایجاد بدترین حالت، یک بهینه سازی با عنوان میانه سه پیشنهاد می شود. به این صورت که برای انتخاب عنصر شاخص دقت بیشتری به خرح می دهیم و در هر فراخوانی میانه عناصر اول، وسط و آخر بخش مورد نظر از آرایه را به عنوان عنصر شاخص انتخاب می کنیم.
این کار در میل کردن به بهترین حالت هم مفید است چرا که امکان دارد اندیس نهایی میانه ای که به عنوان شاخص انتخاب می شود، کمی (یا خیلی!) نزدیک به وسط آرایه باشد و همین موجب می شود در فراخوانی بعدی Quick-sort آرایه تقریباً به دو نیم تقسیم شود که این یعنی نزدیک شدن به بهترین حالت الگوریتم.
به سراغ کد برویم؛ با فرض این که الگوریتم متداول Quicksort به چشمتان آشناست، بیشتر توضیحات داخل کد به صورت نام گذاری های واضح و کامنت گذاری ارائه شده است.
تابع (...) GetMedian برای انتخاب عنصر میانه است.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | int GetMedian(int * Array, int startIndex, int middle, int endIndex) { if (Array[startIndex] <= Array[middle]) { if (Array[middle] <= Array[endIndex]) return middle; else if (Array[startIndex] <= Array[endIndex]) return endIndex; else return startIndex; } else { if (Array[startIndex] <= Array[endIndex]) return startIndex; else if (Array[middle] <= Array[endIndex]) return endIndex; else return middle; } } |
و پیاده سازی تابع (...)Partition
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 | int Partition(int * Array, int startIndex, int endIndex) { int temp; // Temporary variable to use in exchanges int lowerRangeIndex = startIndex - 1; // The lowerRangeIndex variable hold the last index of lower-than-pivot range from startIndex to it // The pivotIndex will assign to the index of median of three element of part that sholud be sorted (the first, middle and last element) int pivotIndex = GetMedian(Array, startIndex, startIndex + ((endIndex - startIndex) / 2), endIndex); int pivotValue = Array[pivotIndex]; // Exchanging the pivot and last element of Array (in range [startIndex ... endIndex]) for simplicity temp = Array[pivotIndex]; Array[pivotIndex] = Array[endIndex]; Array[endIndex] = temp; for (int tempIndex = startIndex; tempIndex < endIndex; tempIndex++) { if (Array[tempIndex] <= pivotValue) { // The next place of lowerRangeIndex is the correct place to hold the next lower-than-pivot element lowerRangeIndex = lowerRangeIndex + 1; //Exchanging Array[lowerRangeIndex] and an element that is lower than pivot temp = Array[lowerRangeIndex]; Array[lowerRangeIndex] = Array[tempIndex]; Array[tempIndex] = temp; } } // Putting the pivot to correct place if (lowerRangeIndex != endIndex) { // The next place of lowerRangeIndex is the correct place to hold the pivot lowerRangeIndex = lowerRangeIndex + 1; // Exchanging the pivot and current value in pivot's correct place temp = Array[lowerRangeIndex]; Array[lowerRangeIndex] = Array[endIndex]; Array[endIndex] = temp; } return lowerRangeIndex; } |
و اما تابع
(...)QuickSort_MedianOfThree
:
1 2 3 4 5 6 7 8 9 10 11 12 13 | void QuickSort_MedianOfThree(int * Array, int startIndex, int endIndex) { if (startIndex < endIndex) { // After running partition() an element called pivot get the correct place in array, // then we will partition the Array in two parts corresponding the pivot index int pivotIndex = Partition(Array, startIndex, endIndex); // Partitioning the Array to two parts, first before the pivot, second after the pivot QuickSort_MedianOfThree(Array, startIndex, pivotIndex - 1); QuickSort_MedianOfThree(Array, pivotIndex + 1, endIndex); } } |
اگر در مشاهده کدها در این صفحه مشکلی داشتید، روی github (در اینجا) در اختیارتان هستند!
برای مطالعه بیشتر می توانید به لینک های زیر مراجعه کنید.
StackOverFlow: median 3 quicksort implementation
Algorithms in C#: quick sort (part three)
Quick Sort Implementation with median-of-three partitioning and cutoff for small arrays
سلام میشه خواهش کنم سورس کد زمان اجرای برنامه رو برای اعداد تصادفی بزارین؟
میتوانید به سادگی با استفاده از هدر time.h و تابع time() این کار را انجام دهید
البته اگر بخوایم صورت‌مساله رو دور بزنیم، باید بگم معمولاً بعد از ثبت رکورد جدید هست که نیاز به سورت کردن پیدا میشه. بهترین کار اینه که یک بار سورت کنیم و بعد از اون برای ثبت هر رکورد، اون رو با توجه به معیارهامون در محل مناسب از آرایه قرار بدیم و دوباره سورت نکنیم 😛
فرشاد خان همون بار اولی رو که می گی چطور می خوای سورت کنی که سریع و بهینه باشه ؟! 😀