โปรแกรม C++ สำหรับ Comb Sort (คอมบ์ซอร์ท)

Comb Sort คล้ายกับ Bubble Sort และ Cocktail Sort Comb Sort ไม่เริ่มดูองค์ประกอบที่อยู่ติดกัน แต่ดูองค์ประกอบที่ห่างกันจำนวนดัชนีหนึ่ง เรียกว่า gap (ช่องว่าง) Gap ถูกกำหนดเป็น [n/c] โดย n คือจำนวนองค์ประกอบ และ c คือ shrink factor หลังจากแต่ละรอบ ตัวเลขนี้จะหารด้วย c อีกครั้งและปัดเศษลง จนกว่าอัลกอริทึมจะดูองค์ประกอบที่อยู่ติดกัน

Input: 5 3 4 2 1
Output: 1 2 3 4 5

คำอธิบาย

Comb Sort เปรียบเทียบสององค์ประกอบด้วย gap ที่กำหนดเป็น [n/c] โดย n คือจำนวนองค์ประกอบ และ c คือ shrink factor คือ 1.3 หลังจากแต่ละรอบ ตัวเลขนี้จะหารด้วย c อีกครั้งและปัดเศษลง จนกว่าจะดูองค์ประกอบที่อยู่ติดกัน

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

void combsort(int a[], int n) {
    int i, j, gap, swapped = 1;
    double temp;
    gap = n;
    while (gap > 1 || swapped == 1) {
        gap = gap * 10 / 13; // gap = gap / 1.3
        if (gap == 9 || gap == 10)
            gap = 11;
        if (gap < 1)
            gap = 1;
        swapped = 0;
        for (i = 0, j = gap; j < n; i++, j++) {
            if (a[i] > a[j]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                swapped = 1;
            }
        }
    }
}

int main() {
    int n, i;
    int arr[] = {5, 3, 4, 2, 1};
    n = 5;
    combsort(arr, n);
    for (i = 0; i < n; i++)
        cout << arr[i] << "\t";
    return 0;
}