«مرتب‌سازی شانه‌ای» (Comb Sort) در حقیقت یک نسخه بهبود یافته از «جستجوی حبابی» (Bubble Sort) است. جستجوی حبابی همیشه مقادیر مجاور را مقایسه می‌کند. بنابراین، همه «لاک‌پشت‌ها» یکی یکی حذف می‌شوند. مرتب‌سازی شانه‌ای، مرتب‌سازی حبابی را با استفاده از شکاف‌های با سایز بالاتر از ۱ بهبود می‌بخشد. شکاف با مقدار زیادی شروع می‌شود و با عاملی از ۱٫۳ در هر تکرار کوچک می‌شود تا به مقدار ۱ برسد. بنابراین، مرتب‌سازی شانه‌ای بیش از یک مقدار لاک‌پشت را حذف و بهتر از مرتب‌سازی حبابی عمل می‌کند.

عامل کوچک شدن به صورت تجربی محاسبه شده و برابر با ۱٫۳ در نظر گرفته می‌شود (با ارزیابی مرتب‌سازی روی بیش از ۲۰۰,۰۰۰ لیست تصادفی). مرتب‌سازی شانه‌ای در حالت متوسط بهتر از مرتب‌سازی حبابی کار می‌کند، اما در بدترین حالت همچنان از درجه (O(n² است.

مرتب سازی شانه ای در ++C

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

مرتب سازی شانه ای در جاوا

// Java program for implementation of Comb Sort 
class CombSort 
{ 
    // 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 arr[] using Comb Sort 
    void sort(int arr[]) 
    { 
        int n = arr.length; 
  
        // initialize gap 
        int gap = n; 
  
        // Initialize swapped as true to make sure that 
        // loop runs 
        boolean 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 (arr[i] > arr[i+gap]) 
                { 
                    // Swap arr[i] and arr[i+gap] 
                    int temp = arr[i]; 
                    arr[i] = arr[i+gap]; 
                    arr[i+gap] = temp; 
  
                    // Set swapped 
                    swapped = true; 
                } 
            } 
        } 
    } 
  
    // Driver method 
    public static void main(String args[]) 
    { 
        CombSort ob = new CombSort(); 
        int arr[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0}; 
        ob.sort(arr); 
  
        System.out.println("sorted array"); 
        for (int i=0; i<arr.length; ++i) 
            System.out.print(arr[i] + " "); 
  
    } 
} 
/* This code is contributed by Rajat Mishra */

مرتب سازی شانه ای در پایتون

# Python program for implementation of CombSort 
  
# To find next gap from current 
def getNextGap(gap): 
  
    # Shrink gap by Shrink factor 
    gap = (gap * 10)/13
    if gap < 1: 
        return 1
    return gap 
  
# Function to sort arr[] using Comb Sort 
def combSort(arr): 
    n = len(arr) 
  
    # Initialize gap 
    gap = n 
  
    # Initialize swapped as true to make sure that 
    # loop runs 
    swapped = True
  
    # Keep running while gap is more than 1 and last 
    # iteration caused a swap 
    while gap !=1 or swapped == 1: 
  
        # 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 i in range(0, n-gap): 
            if arr[i] > arr[i + gap]: 
                arr[i], arr[i + gap]=arr[i + gap], arr[i] 
                swapped = True
  
  
# Driver code to test above 
arr = [ 8, 4, 1, 3, -44, 23, -6, 28, 0] 
combSort(arr) 
  
print ("Sorted array:") 
for i in range(len(arr)): 
    print (arr[i]), 
  
  
# This code is contributed by Mohit Kumra

مرتب سازی شانه ای در #C

// C# program for implementation of Comb Sort 
using System; 
  
class GFG 
{ 
    // To find gap between elements 
    static int getNextGap(int gap) 
    { 
        // Shrink gap by Shrink factor 
        gap = (gap*10)/13; 
        if (gap < 1) 
            return 1; 
        return gap; 
    } 
  
    // Function to sort arr[] using Comb Sort 
    static void sort(int []arr) 
    { 
        int n = arr.Length; 
  
        // 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  
        // ۱ 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 (arr[i] > arr[i+gap]) 
                { 
                    // Swap arr[i] and arr[i+gap] 
                    int temp = arr[i]; 
                    arr[i] = arr[i+gap]; 
                    arr[i+gap] = temp; 
  
                    // Set swapped 
                    swapped = true; 
                } 
            } 
        } 
    } 
  
    // Driver method 
    public static void Main() 
    { 
        int []arr = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0}; 
        sort(arr); 
  
        Console.WriteLine("sorted array"); 
        for (int i=0; i<arr.Length; ++i) 
            Console.Write(arr[i] + " "); 
  
    } 
} 
  
// This code is contributed by Sam007

خروجی قطعه کد بالا به صورت زیر است.

Sorted array:
-۴۴ -۶ ۰ ۱ ۳ ۴ ۸ ۲۳ ۲۸ ۵۶

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

۸, ۴, ۱, ۵۶, ۳, -۴۴, ۲۳, -۶, ۲۸, ۰

مقدار اولیه شکاف = ۱۰

پس از انقباض مقدار شکاف داریم

=> 10/1.3 = 7

۸ ۴ ۱ ۵۶ ۳ -۴۴ ۲۳ -۶ ۲۸ ۰
-۶ ۴ ۱ ۵۶ ۳ -۴۴ ۲۳ ۸ ۲۸ ۰
-۶ ۴ ۰ ۵۶ ۳ -۴۴ ۲۳ ۸ ۲۸ ۱

مقدار جدید شکاف

=> 7/1.3 = 5

-۴۴ ۴ ۰ ۵۶ ۳ -۶ ۲۳ ۸ ۲۸ ۱
-۴۴ ۴ ۰ ۲۸ ۳ -۶ ۲۳ ۸ ۵۶ ۱
-۴۴ ۴ ۰ ۲۸ ۱ -۶ ۲۳ ۸ ۵۶ ۳

مقدار جدید شکاف

=> 5/1.3 = 3

-۴۴ ۱ ۰ ۲۸ ۴ -۶ ۲۳ ۸ ۵۶ ۳
-۴۴ ۱ -۶ ۲۸ ۴ ۰ ۲۳ ۸ ۵۶ ۳
-۴۴ ۱ -۶ ۲۳ ۴ ۰ ۲۸ ۸ ۵۶ ۳
-۴۴ ۱ -۶ ۲۳ ۴ ۰ ۳ ۸ ۵۶ ۲۸

مقدار جدید شکاف

=> 3/1.3 = 2

-۴۴ ۱ -۶ ۰ ۴ ۲۳ ۳ ۸ ۵۶ ۲۸
-۴۴ ۱ -۶ ۰ ۳ ۲۳ ۴ ۸ ۵۶ ۲۸
-۴۴ ۱ -۶ ۰ ۳ ۸ ۴ ۲۳ ۵۶ ۲۸

مقدار جدید شکاف

=> 2/1.3 = 1

-۴۴ -۶ ۱ ۰ ۳ ۸ ۴ ۲۳ ۵۶ ۲۸
-۴۴ -۶ ۰ ۱ ۳ ۸ ۴ ۲۳ ۵۶ ۲۸
-۴۴ -۶ ۰ ۱ ۳ ۴ ۸ ۲۳ ۵۶ ۲۸
-۴۴ -۶ ۰ ۱ ۳ ۴ ۸ ۲۳ ۲۸ ۵۶

no more swaps required (Array sorted)

پیچیدگی زمانی روش بالا در بدترین حالت از درجه (O(n² و در بهترین حالت از درجه (O(n است. فضای کمکی این روش نیز ار درجه (O(1 است.

منبع [+]

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

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• برنامه مرتب‌سازی ماتریس — راهنمای کاربردی
• مرتب‌سازی پشته با الگوریتم بازگشتی — به زبان ساده
• مرتب‌سازی درجی (Insertion Sort) — به زبان ساده