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

Cocktail Sort เป็นการเปลี่ยนแปลงอีกแบบของ Bubble Sort ในเทคนิค Bubble Sort จะค้นหาจากซ้ายไปขวาเสมอ และหาองค์ประกอบมากที่สุดไว้ท้าย ในเฟสที่สอง หาองค์ประกอบมากที่สุดอันดับสองไว้ตำแหน่งรองท้าย เทคนิคการเรียงนี้ท่องในทั้งสองทิศทางสลับกัน มาดูอัลกอริทึมเพื่อเข้าใจแนวคิด

อัลกอริทึม

cocktail(array, n)

Begin
    flag := true
    start := 0, end := n-1
    while flag is set, do
        flag := false
        for i in range start to end-1, do
            if arr[i] > arr[i+1], then
                exchange arr[i] and arr[i+1]
                flag := true
            end if
        done
        if flag is not set, then
            break
        end if
        flag := false
        end := end - 1
        for i in range end - 1 down to start, do
            if arr[i] > arr[i+1], then
                exchange arr[i] and arr[i+1]
                flag := true
            end if
        done
        start := start + 1
    done
End

ตัวอย่าง

#include<iostream>
using namespace std;

void cocktailSort(int arr[], int n) {
    bool flag = true;
    int start = 0, end = n - 1;
    while(flag) {
        flag = false;
        for(int i = start; i < end; i++) { // scan from left to right as bubble sort
            if(arr[i] > arr[i+1]) {
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }
        if(!flag) { // if nothing changed simply break the loop
            break;
        }
        flag = false;
        end--; // decrease the end pointer
        for(int i = end - 1; i >= start; i--) { // scan from right to left
            if(arr[i] > arr[i+1]) {
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }
        start++;
    }
}

int main() {
    int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data) / sizeof(data[0]);
    cout << "Sorted Sequence ";
    cocktailSort(data, n);
    for(int i = 0; i < n; i++) {
        cout << data[i] << " ";
    }
}

ผลลัพธ์

Sorted Sequence 13 20 32 35 40 54 74 98 98 154