الگوریتم مرتب سازی شانه ای (Comb Sort)

الگوریتم مرتب سازی شانه ای (Comb Sort)

ایده اصلی مرتب سازی حبابی و مرتب سازی شانه ای یکی است. به عبارت دیگر می توان گفت که الگوریتم مرتب سازی شانه ای (Comb Sort)، بهبود یافته الگوریتم Bubble Sort است. در روش مرتب سازی حبابی، در هر مرحله هر مقدار با مقدار بعدی مقایسه می شود و میزان شکاف (Gap) همیشه ۱ است. اما در مرتب سازی شانه ای، موارد در یک شکاف خاص طبقه بندی می شوند و بعد از اتمام هر مرحله، اندازه شکاف کاهش می یابد تا به ۱ برسد. ضریب کاهش شکاف ۱٫۳ است. یعنی پس از اتمام هر مرحله شکاف بر ۱٫۳ تقسیم می شود.

پیاده سازی الگوریتم Comb Sort

پیاده سازی الگوریتم مرتب سازی شانه ای با استفاده از زبان برنامه نویسی سی پلاس پلاس :

// C++ implementation of Comb Sort
#include<bits/stdc++.h>
using namespace std;
// To find gap between elements
int getNextGap(int gap)
{
    // Shrink gap by Shrink factor
    gap = (gap*10)/13;
    if (gap < 1)
        return 1;
    return gap;
}
// Function to sort a[0..n-1] using Comb Sort
void combSort(int a[], int n)
{
    // Initialize gap
    int gap = n;
    // Initialize swapped as true to make sure that
    // loop runs
    bool swapped = true;
    // Keep running while gap is more than 1 and last
    // iteration caused a swap
    while (gap != 1 || swapped == true)
    {
        // Find next gap
        gap = getNextGap(gap);
        // Initialize swapped as false so that we can
        // check if swap happened or not
        swapped = false;

        // Compare all elements with current gap
        for (int i=0; i<n-gap; i++)
        {
            if (a[i] > a[i+gap])
            {
                swap(a[i], a[i+gap]);
                swapped = true;
            }
        }
    }
}
// Driver program
int main()
{
    int a[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
    int n = sizeof(a)/sizeof(a[0]);
    combSort(a, n);
    printf("Sorted array: \n");
    for (int i=0; i<n; i++)
        printf("%d ", a[i]);
    return 0;
}

امتحان کنید

خروجی:

Sorted array:
-44 -6 0 1 3 4 8 23 28 56

شبیه سازی

آرایه زیر را در نظر بگیرید (مقدار اولیه شکاف ۱۰ است):

8, 4, 1, 56, 3, -44, 23, -6, 28, 0
مقدار جدید شکاف: 10/1.3 = 7
8 4 1 56 3 -44 23 -6 28 0
-6 4 1 56 3 -44 23  8 28 0
-6 4 0 56 3 -44 23  8 28 1
مقدار جدید شکاف: 7/1.3 = 5
-44 4 0 56 3 -6 23 8 28 1
-44 4 0 28 3 -6 23 8 56 1
-44 4 0 28 1 -6 23 8 56 3
مقدار جدید شکاف: 5/1.3 = 3
-44 1  0 28 4 -6 23 8 56 3
-44 1 -6 28 4  0 23 8 56 3
-44 1 -6 23 4  0 28 8 56 3
-44 1 -6 23 4  0  3 8 56 28
مقدار جدید شکاف: 3/1.3 = 2
-44 1 -6 0 4 23 3 8 56 28
-44 1 -6 0 3 23 4 8 56 28
-44 1 -6 0 3 8 4 23 56 28
مقدار جدید شکاف: 2/1.3 = 1
-44 -6 1 0 3 8 4 23 56 28
-44 -6 0 1 3 8 4 23 56 28
-44 -6 0 1 3 4 8 23 56 28
-44 -6 0 1 3 4 8 23 28 56

نکات

• پیچیدگی زمانی در بهترین حالت: O(n log n)
• پیچیدگی زمانی در حالت متوسط: O(n²/2^p)
• پیچیدگی زمانی در بدترین حالت: O(n²)
• پیچیدگی فضایی: O(1)

نوشته الگوریتم مرتب سازی شانه ای (Comb Sort) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.