โปรแกรม C++ Shaker Sort (Cocktail Sort)

ภาพรวม

Shaker Sort (หรือ Cocktail Sort) เป็นการปรับปรุง Bubble Sort โดยการเรียงลำดับสลับไปมาระหว่างซ้าย-ขวา และขวา-ซ้าย ช่วยให้ค่าที่เล็ก "ลอย" ขึ้นไปด้านหน้า และค่าที่ใหญ่ "จม" ลงไปด้านหลังได้เร็วขึ้น ความซับซ้อนด้านเวลา O(n²) เหมือน Bubble Sort แต่มีประสิทธิภาพดีกว่าจริง

อัลกอริธึม

1. กำหนดตัวแปร left = 0, right = n-1
2. วนลูปจนกว่า left >= right:
   • Forward Pass (ซ้าย→ขวา): วน i = left+1 ถึง right, สลับถ้า arr[i] < arr[i-1] → ค่ามากสุดจะอยู่ที่ right
   • right--
   • Backward Pass (ขวา→ซ้าย): วน i = right ถึง left+1, สลับถ้า arr[i] < arr[i-1] → ค่าน้อยสุดจะอยู่ที่ left
   • left++

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

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

void swap(int& a, int& b) {
    int temp = a; a = b; b = temp;
}

void shakerSort(vector& arr) {
    int left = 0;
    int right = arr.size() - 1;
    
    while (left < right) {
        // Forward pass: บนไปล่าง (ค่ามากจมขวา)
        for (int i = left + 1; i <= right; i++) {
            if (arr[i] < arr[i-1]) swap(arr[i], arr[i-1]);
        }
        right--;
        
        // Backward pass: ล่างขึ้นบน (ค่าน้อยลอยซ้าย)
        for (int i = right; i > left; i--) {
            if (arr[i] < arr[i-1]) swap(arr[i], arr[i-1]);
        }
        left++;
    }
}

int main() {
    int n;
    cout << "Enter the number of data elements to be sorted: ";
    cin >> n;
    
    vector arr(n);
    for (int i = 0; i < n; i++) {
        cout << "Enter element " << i+1 << ": ";
        cin >> arr[i];
    }
    
    shakerSort(arr);
    
    cout << "\nSorted Data: ";
    for (int val : arr) cout << "->" << val;
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter the number of data elements to be sorted: 4
Enter element 1: 3
Enter element 2: 1
Enter element 3: 7
Enter element 4: 6
Sorted Data: ->1->3->6->7

การเปรียบเทียบกับ Bubble Sort