การเรียงลำดับแบบ Shell Sort ใน Python

บทนำ

Shell Sort เป็นอัลกอริทึมการเรียงลำดับที่ปรับปรุงจาก Insertion Sort โดยการเปรียบเทียบและสลับข้อมูลที่ห่างกันตาม "ช่วง" (interval/gap) ซึ่งลดลงเรื่อยๆ จนเหลือ 1 ทำให้ข้อมูลเคลื่อนที่ได้ไกลกว่าและมีประสิทธิภาพดีกว่า

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

def shell_sort(arr):
    """Shell Sort แบบ in-place"""
    n = len(arr)
    gap = n // 2  # เริ่มต้น gap ที่ครึ่งหนึ่งของขนาด

    while gap > 0:
        # Insertion sort สำหรับแต่ละ sublist ที่ห่างกัน gap
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # เลื่อนค่าที่มากกว่า temp ไปทางขวา
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # ลด gap ลงครึ่งหนึ่ง
    return arr

# ทดสอบ
my_list = [45, 31, 62, 12, 89, 5, 9, 8]
print("ก่อนเรียง:", my_list)
sorted_list = shell_sort(my_list)
print("หลังเรียง:", sorted_list)

ผลลัพธ์

ก่อนเรียง: [45, 31, 62, 12, 89, 5, 9, 8]
หลังเรียง: [5, 8, 9, 12, 31, 45, 62, 89]

คำอธิบายขั้นตอน

1. คำนวณ gap เริ่มต้น = n // 2
2. ทำ Insertion Sort บน sublist ที่ห่างกัน gap (เช่น index 0, gap, 2*gap, ...)
3. ลด gap ลงครึ่งหนึ่ง (gap //= 2)
4. ทำซ้ำจน gap = 1 (กลายเป็น Insertion Sort ธรรมดา แต่ข้อมูลใกล้เรียงแล้ว)

ความซับซ้อน

• เวลา: O(n²) หรุดกว่า (ขึ้นอยู่กับ gap sequence) โดยเฉลี่ย ~O(n^1.25)
• พื้นที่: O(1) (in-place)
• ไม่เสถียร (Unstable) - อาจสลับลำดับค่าที่เท่ากัน