โปรแกรม C++ อัลกอริทึม Shell Sort

Shell Sort

เทคนิคการจัดเรียงแบบ Shell Sort พัฒนามาจากการจัดเรียงแบบแทรก (Insertion Sort) ใน Insertion Sort บางครั้งเราต้องเลื่อนบล็อกขนาดใหญ่เพื่อแทรกไอเท็มในตำแหน่งที่ถูกต้อง การใช้ Shell Sort ช่วยหลีกเลี่ยงการเลื่อนจำนวนมากได้ การจัดเรียงทำงานด้วยช่วงระยะ (interval) เฉพาะ หลังจากแต่ละรอบ ช่วงระยะจะลดลงเพื่อทำให้ช่วงระยะเล็กลง

ความซับซ้อนของ Shell Sort

• Time Complexity: O(n log n) สำหรับกรณีดีที่สุด และในกรณีอื่นๆ ขึ้นอยู่กับลำดับช่วงว่าง (gap sequence)

• Space Complexity: O(1)

Input - รายการที่ไม่ได้จัดเรียง: 23 56 97 21 35 689 854 12 47 66
Output - Array after Sorting: 12 21 23 35 47 56 66 97 689 854

อัลกอริทึม

shellSort(array, size)

Input: อาร์เรย์ข้อมูล, และจำนวนรวมในอาร์เรย์

Output: อาร์เรย์ที่จัดเรียงแล้ว

เริ่มต้น
  for gap := size / 2, เมื่อ gap > 0 และ gap อัปเดตด้วย gap / 2
    for j := gap ถึง size-1
      for k := j-gap ถึง 0, ลดลงตามค่า gap
        if array[k+gap] >= array[k]
          break
        else
          สลับ array[k + gap] กับ array[k]
      done
    done
  done
สิ้นสุด

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

#include <iostream>
using namespace std;

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

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

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

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];
    cout << "Enter elements:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    shellSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

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

Enter the number of elements: 10
Enter elements: 23 56 97 21 35 689 854 12 47 66
Array before Sorting: 23 56 97 21 35 689 854 12 47 66
Array after Sorting: 12 21 23 35 47 56 66 97 689 854