Thuật toán sắp xếp Shell với VÍ DỤ

Sắp xếp Shell là gì

Phương pháp của Shell hoặc Sắp xếp Shell trong Cấu trúc dữ liệu là một thuật toán sắp xếp so sánh tại chỗ hiệu quả. Nó được đặt theo tên của Donald Shell khi ông đề xuất ý tưởng ban đầu vào năm 1959. Sắp xếp Shell là một phần mở rộng tổng quát của thuật toán sắp xếp chèn.

Ý tưởng cơ bản của thuật toán sắp xếp này là nhóm các phần tử cách xa nhau và sắp xếp chúng theo đó. Sau đó, giảm dần khoảng cách giữa chúng. Shell sort khắc phục được độ phức tạp thời gian trường hợp trung bình của thuật toán sắp xếp chèn bằng cách so sánh và trao đổi các phần tử cách xa nhau.

Khoảng cách này, được gọi là khoảng, được giảm theo một số chuỗi khoảng cách tối ưu. Thời gian chạy của sắp xếp shell cũng phụ thuộc vào các trình tự này. Có một số chuỗi khoảng trống, chẳng hạn như chuỗi khoảng trống ban đầu của Shell, công thức Knuth, số gia của Hibbard, v.v. Chuỗi khoảng trống ban đầu của Shell là – n/2, n/4, n/8, ……….1

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

Các bước hoặc quy trình cho thuật toán sắp xếp shell như sau-

Bước 1) Khởi tạo giá trị khoảng, h = n/2. (Trong ví dụ này, n là kích thước của mảng)

Bước 2) Đặt tất cả các phần tử trong khoảng cách h vào danh sách phụ.

Bước 3) Sắp xếp các danh sách phụ đó bằng cách sử dụng phương pháp 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 thì chuyển sang bước 2. Ngược lại thì chuyển sang bước 6.

Bước 6) Kết quả đầu ra sẽ là mảng được sắp xếp.

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

Trong sắp xếp chèn, các phần tử chỉ được di chuyển một vị trí tại một thời điểm. Ngược lại, sắp xếp shell chia mảng thành các phần nhỏ hơn dựa trên giá trị khoảng và thực hiện sắp xếp chèn trên các phần đó.

Dần dần, giá trị khoảng giảm dần và kích thước của các phần được chia tăng lên. Vì các phần đã được sắp xếp riêng lẻ từ trước nên việc hợp nhất các phần đó đòi hỏi ít bước hơn so với sắp xếp chèn.

GIF sau đây cho thấy một bản trình diễn về sắp xếp shell. Trong bản demo này, giá trị được chỉ định màu đỏ và màu xanh lam được so sánh và hoán đổi dựa trên sắp xếp chèn. Sau đó, khoảng thời gian giảm xuống và sắp xếp shell khởi tạo sắp xếp chèn trong dữ liệu gần như đã được sắp xếp đó.

Hoạt động của thuật toán sắp xếp Shell

Chúng ta hãy xem ví dụ sau về thuật toán shell sort. Trong ví dụ này, chúng ta sẽ sắp xếp mảng sau bằng shell sort:

Bước 1) Ở đây, kích thước mảng là 8. Do đó, giá trị khoảng sẽ là h = 8/2 hoặc 4.

Bước 2) Bây giờ, chúng tôi sẽ lưu trữ tất cả các phần tử ở khoảng cách 4. Trong trường hợp của chúng tôi, các danh sách con là- {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Bước 3) Bây giờ, các danh sách con đó sẽ được sắp xếp bằng cách sử dụng phương pháp sắp xếp chèn, trong đó một biến tạm thời được sử dụng để so sánh cả hai số và sắp xếp tương ứng.

Mảng sẽ như sau sau khi thực hiện các thao tác hoán đổi:

Bước 4) Bây giờ, chúng ta sẽ giảm giá trị ban đầu của khoảng. Khoảng mới sẽ là h=h/2 hoặc 4/2 hoặc 2.

Bước 5) Vì 2>0, chúng ta sẽ chuyển sang bước 2 để lưu trữ tất cả các phần tử ở khoảng cách 2. Lần này, các danh sách con là-

{1, 5, 8, 7}, {4, 2, 6, 3}

Sau đó, các danh sách con này sẽ được sắp xếp bằng phương pháp sắp xếp chèn. Sau khi so sánh và hoán đổi danh sách con đầu tiên, mảng sẽ như sau.

Sau khi sắp xếp danh sách con thứ hai, mảng ban đầu sẽ là:

Sau đó, một lần nữa, khoảng thời gian sẽ giảm. Bây giờ khoảng sẽ là h=h/2 hoặc 2/1 hoặc 1. Do đó chúng ta sẽ sử dụng thuật toán sắp xếp chèn để sắp xếp mảng đã sửa đổi.

Sau đây là mô tả thủ tục từng bước của thuật toán sắp xếp chèn.

Khoảng này lại được chia cho 2. Lúc này, khoảng đó trở thành 0. Vì vậy chúng ta chuyển sang bước 6.

Bước 6) Vì khoảng bằng 0, mảng được sắp xếp theo thời gian này. Mảng được sắp xếp là-

Mã giả

Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
    for (i = interval; i & lt; n; i += 1)
        temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; 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

Dưới đây là những ứng dụng quan trọng của Shell Sort:

Sắp xếp Shell được sử dụng trong Linux kernel bởi vì nó không sử dụng ngăn xếp cuộc gọi.
Thư viện uClibc sử dụng sắp xếp Shell.
Máy nén bzip2 sử dụng Shell Sort để dừng vượt quá đệ quy.

Ưu điểm và nhược điểm của Shell Sort

Ưu điểm	Nhược điểm
Không cần cuộc gọi ngăn xếp.	Không hiệu quả đối với kích thước mảng lớn.
Thực hiện dễ dàng.	Không hiệu quả đối với các yếu tố phổ biến rộng rãi.
Hiệu quả cho các phần tử có khoảng cách ít hơn.

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 thời gian của thuật toán sắp xếp shell là O(n^2). Lý luận như sau:

Trong trường hợp tốt nhất, tổng số lượng bài kiểm tra cho tất cả các khoảng thời gian khi mảng được sắp xếp trước đó bằng log n. Do đó, độ phức tạp sẽ là O(n*log n).

Đối với trường hợp xấu nhất, hãy xem xét mảng bao gồm theo cách mà các phần tử yêu cầu số lượng so sánh cao nhất. Khi đó tất cả các phần tử sẽ không được so sánh và chuyển đổi cho đến lần lặp cuối cùng. Do đó, tổng số so sánh cần thiết cho mức tăng cuối cùng là O(n^2).

Tóm lại, độ phức tạp về thời gian sẽ là

Độ phức tạp trường hợp tốt nhất: O(n*log n)
Độ phức tạp trường hợp trung bình: O(n*log n)
Độ phức tạp trường hợp xấu nhất: O(n^2)

Độ phức tạp về thời gian chạy của shell sort phụ thuộc rất nhiều vào chuỗi gia số khoảng cách được sử dụng. Tuy nhiên, chuỗi gia số tốt nhất cho shell sort vẫn chưa được biết.

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

Trong loại so sánh này, chúng ta không cần bất kỳ không gian bổ trợ nào. Do đó, độ phức tạp không gian của loại thuật toán này là O(1).

Bạn có thể thích: