Thuật toán sắp xếp Shell kèm ví dụ

Shell Sort là gì?

Thuật toán Shell Sort, hay còn gọi là phương pháp Shell, là một thuật toán sắp xếp hiệu quả dựa trên so sánh tại chỗ. Được đặt theo tên của Donald Shell, người đã giới thiệu ý tưởng này vào năm 1959, nó là một phần mở rộng tổng quát của thuật toán sắp xếp chèn, khắc phục được nhược điểm về độ phức tạp bậc hai trên dữ liệu phân tán.

Ý tưởng cơ bản là nhóm các phần tử cách xa nhau lại với nhau, sắp xếp từng nhóm bằng thuật toán sắp xếp chèn, và thu hẹp khoảng cách từng bước cho đến khi đạt đến một. Khi đó, mảng gần như đã được sắp xếp xong.

Khoảng trống này, hay quãng nghỉ, tuân theo một trình tự đã chọn, chẳng hạn như trình tự gốc của Shell, Knuth, Hibbard hoặc Sedgewick. Trình tự gốc của Shell là... n/2, n/4, ..., 1.

Thuật toán sắp xếp Shell

Bước 1) Khởi tạo giá trị khoảng h = n/2, trong đó n là kích thước của mảng.

Bước 2) Đưa tất cả các phần tử nằm trong khoảng cách h vào một danh sách con.

Bước 3) Sắp xếp từng danh sách con bằng thuật toán sắp xếp chèn.

Bước 4) Đặt khoảng thời gian mới h = h/2.

Bước 5) Nếu h > 0, quay lại Bước 2. Nếu không, chuyển đến Bước 6.

Bước 6) Mảng kết quả hiện đã được sắp xếp hoàn toàn.

Cách thức hoạt động của Shell Sort

Trong thuật toán sắp xếp chèn, các phần tử chỉ di chuyển một vị trí mỗi lần. Ngược lại, thuật toán Shell Sort chia mảng thành các danh sách con cách xa nhau dựa trên khoảng và thực hiện sắp xếp chèn trên từng danh sách con.

Khi khoảng thời gian thu hẹp, kích thước danh sách con tăng lên. Vì các lần xử lý trước đó để lại dữ liệu được sắp xếp một phần, nên các khoảng thời gian nhỏ hơn yêu cầu ít thao tác hoán đổi hơn nhiều so với việc chạy liên tục. sắp xếp chèn Từ đầu. Hình dưới đây minh họa một lượt xử lý của Shell Sort.

Nguyên lý hoạt động của thuật toán sắp xếp Shell kèm ví dụ.

Hãy sắp xếp mảng bên dưới bằng Shell Sort.

Bước 1) Kích thước mảng là 8, vì vậy giá trị khoảng ban đầu là h = 8/2 = 4.

Bước 2) Nhóm các phần tử cách nhau bốn vị trí. Danh sách con: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Bước 3) Sắp xếp từng danh sách con bằng thuật toán sắp xếp chèn. Một biến tạm thời lưu giữ giá trị được chèn trong khi các phần tử được dịch chuyển. Sau khi hoán đổi, mảng sẽ trông như thế này.

Bước 4) Giảm khoảng cách. Khoảng cách mới là h = 4/2 = 2.

Bước 5) Vì 2 > 0, hãy quay lại Bước 2 và nhóm các phần tử cách nhau hai vị trí: {1, 5, 8, 7} và {4, 2, 6, 3}.

Sắp xếp danh sách con đầu tiên. Mảng sẽ trở thành:

Sau khi sắp xếp danh sách con thứ hai:

Giảm khoảng cách xuống còn h = 2/2 = 1. Với khoảng cách là một, Shell Sort thực hiện một lượt sắp xếp chèn cuối cùng trên toàn bộ mảng, như hình bên dưới.

Bước 6) Chia khoảng đó một lần nữa sẽ cho kết quả là 0. Mảng hiện đã được sắp xếp hoàn toàn:

giả-Code để sắp xếp Shell

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
            a[j] = a[j - interval];
        a[j] = temp;
End

Chương trình sắp xếp Shell trong C/C++

Đầu vào:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Đầu ra:

Sorted Output:

1 2 3 4 5 6 7 8

Ví dụ sắp xếp Shell trong Python

Đầu vào:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Đầu ra:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Các ứng dụng của Shell Sort

Thuật toán Shell Sort vẫn xuất hiện trong các hệ thống hiện đại khi không gian ngăn xếp hoặc sự đơn giản là yếu tố quan trọng.

• Linux kernel Sử dụng Shell Sort ở những nơi cần tránh tạo ngăn xếp lệnh gọi.
• Thư viện C nhúng uClibc sử dụng thuật toán Shell Sort để giữ mức sử dụng bộ nhớ ở mức thấp.
• bzip2 sử dụng Shell Sort để tránh đệ quy sâu trong quá trình sắp xếp khối.
• Phần mềm nhúng ưu tiên Shell Sort đối với các tập dữ liệu nhỏ, nơi việc sử dụng đệ quy bị hạn chế.

Ưu điểm và nhược điểm của phương pháp phân loại vỏ sò

Phân tích độ phức tạp của Shell Sort

Độ phức tạp thời gian của Shell Sort

Độ phức tạp về thời gian của thuật toán Shell Sort phụ thuộc vào chuỗi khoảng trống được sử dụng.

Trong trường hợp tốt nhất, khi mảng đã gần như được sắp xếp xong, mỗi lượt chỉ cần một số lượng phép thử logarit, cho độ phức tạp O(n log n).

Trong trường hợp xấu nhất, mảng được sắp xếp sao cho các phần tử cần số phép so sánh tối đa và phép tăng cuối cùng chiếm ưu thế ở mức O(n^2) với chuỗi ban đầu của Shell.

1. Độ phức tạp trong trường hợp tốt nhất: O(n log n)
2. Độ phức tạp trung bình: O(n log n) đến O(n^(4/3)) tùy thuộc vào chuỗi khoảng cách
3. Độ phức tạp trong trường hợp xấu nhất: O(n^2) với chuỗi gốc của Shell

Chuỗi khoảng trống đa năng tốt nhất vẫn là một câu hỏi nghiên cứu mở, mặc dù các chuỗi Sedgewick và Ciura hoạt động tốt trong thực tế.

Độ phức tạp của không gian sắp xếp Shell

Shell Sort không yêu cầu mảng phụ trợ, do đó độ phức tạp không gian là O(1) bất kể kích thước đầu vào, đây là một trong những ưu điểm thực tiễn mạnh nhất của nó.

Câu Hỏi Thường Gặp