โปรแกรม C++ สำหรับ Comb Sort

แนวคิดพื้นฐานของ Comb Sort และ Bubble Sort เหมือนกัน กล่าวอีกนัยหนึ่ง Comb Sort เป็นการปรับปรุงจาก Bubble Sort ในเทคนิค Bubble Sort รายการจะถูกเปรียบเทียบกับรายการถัดไปในแต่ละเฟส แต่สำหรับ Comb Sort รายการจะถูกเรียงในช่องว่าง (gap) เฉพาะ หลังจบแต่ละเฟส ช่องว่างจะลดลง ปัจจัยการลดหรือ shrink factor สำหรับการเรียงนี้คือ 1.3 หมายความว่าหลังจบแต่ละเฟส ช่องว่างจะถูกหารด้วย 1.3 Time Complexity คือ O(n log n) สำหรับ best case O(n^2/2^n^P) (p คือจำนวนการเพิ่ม) สำหรับ average case และ O(n^2) สำหรับ worst case

อัลกอริทึม

CombSort(array, size)

Input − อาร์เรย์ข้อมูล และจำนวนรวมในอาร์เรย์

Output − อาร์เรย์ที่เรียงแล้ว

Begin
    gap := size
    flag := true
    while gap ≠ 1 OR flag = true do
        gap = floor(gap/1.3) // take floor value after division
        if gap < 1 then
            gap := 1
        flag = false
        for i := 0 to size - gap - 1 do
            if array[i] > array[i+gap] then
                swap array[i] with array[i+gap]
                flag = true;
            done
    done
End

ตัวอย่าง

#include<iostream>
#include<algorithm>
using namespace std;

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void combSort(int *array, int size) {
    int gap = size; // initialize gap size with size of array
    bool flag = true;
    while(gap != 1 || flag == true) {
        gap = (gap * 10) / 13; // minimize gap by shrink factor
        if(gap < 1)
            gap = 1;
        flag = false;
        for(int i = 0; i < size - gap; i++) { // compare elements with gap
            if(array[i] > array[i + gap]) {
                swap(array[i], array[i + gap]);
                flag = true;
            }
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n]; // create an array with given number of elements
    cout << "Enter elements:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    combSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

ผลลัพธ์

Enter the number of elements: 10
Enter elements: 108 96 23 74 12 56 85 42 13 47
Array before Sorting: 108 96 23 74 12 56 85 42 13 47
Array after Sorting: 12 13 23 42 47 56 74 85 96 108