Chương trình C++ triển khai thuật toán Shell Sort

Kỹ thuật sắp xếp Shell (Shell Sort) dựa trên sắp xếp chèn (Insertion Sort). Trong sắp xếp chèn, đôi khi chúng ta cần dịch chuyển khối lớn để chèn mục vào vị trí đúng. Sử dụng Shell Sort, chúng ta có thể tránh số lượng dịch chuyển lớn. Việc sắp xếp được thực hiện với khoảng cách (interval) cụ thể. Sau mỗi lượt, khoảng cách được giảm để tạo khoảng cách nhỏ hơn.

Độ phức tạp của kỹ thuật Shell Sort

• Độ phức tạp thời gian: O(n log n) cho trường hợp tốt nhất, và đối với các trường hợp khác, phụ thuộc vào chuỗi khoảng cách (gap sequence).
• Độ phức tạp không gian: O(1)

Đầu vào — Danh sách chưa sắp xếp: 23 56 97 21 35 689 854 12 47 66
Đầu ra — Mảng sau khi sắp xếp: 12 21 23 35 47 56 66 97 689 854

Thuật toán

shellSort(array, size)

Đầu vào: Mảng dữ liệu, và tổng số phần tử trong mảng

Đầu ra: Mảng đã sắp xếp

Bắt đầu
    for gap := size / 2, khi gap > 0 và gap cập nhật gap / 2
        for j := gap đến size-1
            for k := j-gap đến 0, giảm theo giá trị gap
                if array[k+gap] >= array[k]
                    break
                else
                    hoán đổi array[k + gap] với array[k]
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

void swapping(int &a, int &b) {
    int 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 << "Nhập số lượng phần tử: ";
    cin >> n;
    int arr[n];
    cout << "Nhập các phần tử:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Mảng trước khi sắp xếp: ";
    display(arr, n);
    shellSort(arr, n);
    cout << "Mảng sau khi sắp xếp: ";
    display(arr, n);
}

Kết quả đầu ra

Nhập số lượng phần tử: 10
Nhập các phần tử: 23 56 97 21 35 689 854 12 47 66
Mảng trước khi sắp xếp: 23 56 97 21 35 689 854 12 47 66
Mảng sau khi sắp xếp: 12 21 23 35 47 56 66 97 689 854