home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

Shell Sort (การจัดเรียงแบบเชลล์)

Shell Sort เป็นการปรับปรุงจาก Insertion Sort โดยเปรียบเทียบและสลับองค์ประกอบที่ห่างกันด้วย Gap (ช่องว่าง) ลดการเลื่อนข้อมูลจำนวนมากเมื่อค่าน้อยอยู่ไกลตำแหน่งที่ควรเป็น

ความซับซ้อน (Complexity)

กรณี Time Complexity
Best Case O(n log n)
Average Case ขึ้นอยู่กับ Gap Sequence (ประมาณ O(n^1.25) ถึง O(n^1.5))
Worst Case O(n²) (Gap sequence แบบเดิม)

Space Complexity: O(1) (In-place)

Gap Sequences ที่นิยม

Sequence Formula Worst Case
Shell (Original) n/2, n/4, ..., 1 O(n²)
Hibbard 2^k - 1: 1, 3, 7, 15, ... O(n^1.5)
Sedgewick 4^k + 3·2^(k-1) + 1: 1, 5, 19, 41, ... O(n^1.33)
Pratt 2^p·3^q: 1, 2, 3, 4, 6, 8, 9, 12, ... O(n log² n)
Tokuda ceil((9·(9/4)^k - 4)/5) O(n^1.25) - ค่อนข้างดีในทางปฏิบัติ

แนวคิดการทำงาน (Original Shell Sequence)

  1. gap = n/2
  2. ทำ Insertion Sort บนแต่ละ "Sub-array" ที่ห่างกัน gap
  3. gap = gap / 2
  4. ทำซ้ำจน gap = 1 (Insertion Sort ปกติรอบสุดท้าย)

ตัวอย่างข้อมูล

Input:  23 56 97 21 35 689 854 12 47 66
Output: 12 21 23 35 47 56 66 97 689 854

อัลกอริทึม (Pseudocode)

shellSort(array, size)
  for gap = size/2; gap > 0; gap /= 2:
    for j = gap to size-1:
      for k = j-gap; k >= 0; k -= gap:
        if array[k+gap] >= array[k]: break
        swap(array[k+gap], array[k])

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

#include <iostream>
using namespace std;

void shellSort(int *arr, int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int j = gap; j < n; j++) {
            for (int k = j - gap; k >= 0; k -= gap) {
                if (arr[k+gap] >= arr[k]) break;
                swap(arr[k+gap], arr[k]);
            }
        }
    }
}

void display(int *array, int size) {
    for (int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

int main() {
    int n; cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << "Before: "; display(arr, n);
    shellSort(arr, n);
    cout << "After: "; display(arr, n);
}

คุณสมบัติ

  • In-place: O(1) space
  • Not Stable: การสลับแบบ Gap อาจเปลี่ยนลำดับค่าเท่ากัน
  • Adaptive: เร็วขึ้นถ้าข้อมูลเรียงแล้วบางส่วน

เมื่อไหร่ควรใช้?

  • ข้อมูลขนาดกลาง (ไม่ใหญ่จนต้อง Merge/Quick/Heap)
  • Embedded Systems: โค้ดสั้น ไม่ต้อง Recursion/Stack
  • เมื่อต้องการ In-place และง่ายกว่า Quick Sort