Gnome Sort คืออะไร?
Gnome Sort (หรือ Stupid Sort) เป็นอัลกอริทึมเรียงลำดับที่ง่ายคล้าย Insertion Sort แต่ทำงานแบบ "เดินไปมา" ตรวจสอบค่าปัจจุบันกับค่าก่อนหน้า:
- ถ้าค่าปัจจุบัน >= ค่าก่อนหน้า → เดินไปข้างหน้า (index++)
- ถ้าค่าปัจจุบัน < ค่าก่อนหน้า → สลับ แล้วเดินถอยหลัง (index--)
- ที่ index 0 → เดินไปข้างหน้าอัตโนมัติ
ตัวอย่างโค้ด
import java.util.Arrays;
public class Demo {
static void gnomeSort(int[] arr, int n) {
int index = 0;
while (index < n) {
if (index == 0) {
index++;
} else if (arr[index] >= arr[index - 1]) {
index++; // เรียงถูกต้องแล้ว ไปต่อ
} else {
// สลับแล้วถอยหลังตรวจสอบอีก
int temp = arr[index];
arr[index] = arr[index - 1];
arr[index - 1] = temp;
index--;
}
}
}
public static void main(String[] args) {
int[] arr = {34, 67, 89, 11, 0, -21};
System.out.println("ก่อน: " + Arrays.toString(arr));
gnomeSort(arr, arr.length);
System.out.println("หลัง: " + Arrays.toString(arr));
}
}
ผลลัพธ์
ก่อน: [34, 67, 89, 11, 0, -21] หลัง: [-21, 0, 11, 34, 67, 89]
คำอธิบายการทำงาน
Gnome Sort เหมือนคนแคระ (gnome) กำลังจัดกระถางต้นไม้: เดินไปข้างหน้าถ้าสมดุล ถ้าหลุดลำดับก็ยกสลับแล้วถอยหลังตรวจสอบต่อ
Trace ตัวอย่าง (arr = [3, 2, 1])
index=0: [3,2,1] -> index=1 (index==0) index=1: [3,2,1] 3>2 -> swap -> [2,3,1], index=0 index=0: [2,3,1] -> index=1 index=1: [2,3,1] 3>=2 -> index=2 index=2: [2,3,1] 1<3 -> swap -> [2,1,3], index=1 index=1: [2,1,3] 1<2 -> swap -> [1,2,3], index=0 index=0: -> index=1 index=1: 2>=1 -> index=2 index=2: 3>=2 -> index=3 (จบ) Result: [1,2,3]
ความซับซ้อน
| กรณี | Time | Space |
|---|---|---|
| Best (Sorted) | O(n) | O(1) |
| Average | O(n²) | O(1) |
| Worst (Reverse) | O(n²) | O(1) |
คุณสมบัติ
- In-place - ไม่ต้องการพื้นที่เพิ่ม
- Stable - รักษาลำดับเดิมของค่าเท่ากัน
- Adaptive - เร็วขึ้นหากข้อมูลเรียงบางส่วนแล้ว
- ไม่ใช้ nested loops - โค้ดสั้น มีแค่ while loop เดียว
เมื่อไหร่ควรใช้
- ข้อมูลเล็ก (n < 50)
- ข้อมูลใกล้เรียงแล้ว (near-sorted)
- การศึกษา / ทดสอบความคิด (ไม่เหมาะ production)
