Cocktail Sort (Bidirectional Bubble Sort)
Cocktail Sort หรือ Shaker Sort เป็นการปรับปรุง Bubble Sort โดยวนลูปสลับทิศทาง: ซ้าย→ขวา แล้ว ขวา→ซ้าย ทำให้ "Turtles" (ค่าน้อยที่อยู่ท้าย) เคลื่อนที่ได้เร็วขึ้น
ตัวอย่างโค้ด
public class Demo {
static int temp;
static void cocktailSort(int[] arr, int n) {
boolean swapped = true;
int begin = 0;
int end = n - 1;
while (swapped) {
swapped = false;
// Pass 1: Left to Right (bubble largest to end)
for (int i = begin; i < end; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // เรียงแล้ว
swapped = false;
end--; // ตัวสุดท้ายเรียงแล้ว
// Pass 2: Right to Left (bubble smallest to front)
for (int i = end - 1; i >= begin; i--) {
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
begin++; // ตัวแรกเรียงแล้ว
}
}
public static void main(String[] args) {
int[] arr = {34, 78, 90, 32, 67, 12, 1, 0, 95};
System.out.println("ก่อน: " + Arrays.toString(arr));
cocktailSort(arr, arr.length);
System.out.println("หลัง: " + Arrays.toString(arr));
}
}
ผลลัพธ์
ก่อน: [34, 78, 90, 32, 67, 12, 1, 0, 95]
หลัง: [0, 1, 12, 32, 34, 67, 78, 90, 95]
คำอธิบายการทำงาน
- Forward Pass (ซ้าย→ขวา): เหมือน Bubble Sort ย้ายค่ามากสุดไปขวาสุด
- Backward Pass (ขวา→ซ้าย): ย้ายค่าน้อยสุดไปซ้ายสุด
- Shrink Range: หลังแต่ละ pass ลด range ลง (begin++, end--) เพราะปลายทั้งสองเรียงแล้ว
- Early Termination: หากไม่มี swap ใน forward pass → เรียงแล้ว หยุดทันที
Trace (arr = [5, 1, 4, 2, 3])
Initial: [5, 1, 4, 2, 3], begin=0, end=4
Forward:
[1,5,4,2,3] swap(0,1)
[1,4,5,2,3] swap(1,2)
[1,4,2,5,3] swap(2,3)
[1,4,2,3,5] swap(3,4) -> 5 at end
swapped=true, end=3
Backward:
[1,4,2,3,5] i=2: 2<3 no swap
[1,4,2,3,5] i=1: 4>2 swap -> [1,2,4,3,5]
[1,2,4,3,5] i=0: 1<2 no swap
swapped=true, begin=1
Forward (range 1..3):
[1,2,4,3,5] i=1: 2<4 no
[1,2,4,3,5] i=2: 4>3 swap -> [1,2,3,4,5]
swapped=true, end=2
Backward (range 1..2):
i=1: 2<3 no swap
swapped=false -> BREAK
Result: [1,2,3,4,5]
ความซับซ้อน
| กรณี | Time | Space |
|---|
| Best (Sorted) | O(n) | O(1) |
| Average | O(n²) | O(1) |
| Worst (Reverse) | O(n²) | O(1) |
เปรียบเทียบ
| Algorithm | Best | Avg | Worst | Stable | Note |
|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Yes | Slow |
| Cocktail Sort | O(n) | O(n²) | O(n²) | Yes | Better for turtles |
| Comb Sort | O(n log n) | O(n log n) | O(n²) | No | Gap-based |
| Insertion Sort | O(n) | O(n²) | O(n²) | Yes | Best for small/near-sorted |
ข้อควรระวัง
- ยังคงเป็น O(n²) worst case - ไม่แทนที่ O(n log n) algorithms
- เหมาะสำหรับ: Nearly sorted data, Small arrays, Educational purposes
- Production: ใช้
Arrays.sort()
