Shell sort có tốt không?

Trong sắp xếp, chúng ta có một số loại thuật toán cơ bản có thể sắp xếp các phần tử theo một thứ tự cụ thể. Chúng ta thường sử dụng một mảng và sắp xếp các phần tử của nó theo thứ tự số và từ điển

Shell sort là phiên bản mở rộng và cải tiến của sắp xếp chèn. Trong sắp xếp chèn, chúng ta lấy một phần tử và so sánh nó với các phần tử trước đó để kiểm tra xem nó nhỏ hơn hay lớn hơn. Sau đó, chúng tôi hoán đổi các số tương ứng nơi diễn ra việc hoán đổi giữa hai phần tử liền kề

Vì sắp xếp hệ vỏ là một biến thể của sắp xếp chèn, ở đây, chúng tôi thực hiện mọi thứ hơi khác một chút cho đến khi cuối cùng chúng tôi có thể áp dụng sắp xếp chèn

Shell Sắp xếp là gì?

Sắp xếp vỏ là một thuật toán sắp xếp và một biến thể mở rộng của sắp xếp chèn với độ phức tạp thời gian trung bình được cải thiện. Trong thuật toán sắp xếp này, chúng tôi so sánh các giá trị ngoài cùng bên phải với các giá trị ngoài cùng bên trái và cố gắng dịch chuyển các giá trị nhỏ hơn ở phía bên trái và các giá trị lớn hơn ở phía bên phải

Vì thuật toán này là một phần mở rộng của sắp xếp chèn, nên nó cũng sử dụng sắp xếp chèn. Ở đây chúng tôi so sánh các giá trị bên trái với các giá trị bên phải dựa trên khoảng cách hoặc khoảng thời gian. Khi chúng ta sử dụng khoảng cách để so sánh các phần tử ở xa, với mỗi bộ so sánh, chúng ta sẽ giảm giá trị của khoảng cách. Khi thuật toán đạt đến điểm có giá trị khoảng cách là 1, nó sẽ sử dụng sắp xếp chèn

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

Điểm quan trọng

• Đây là thuật toán sắp xếp không ổn định vì các phần tử có cùng giá trị có thể thay đổi thứ tự sắp xếp của chúng.
• Đây là một thuật toán sắp xếp nội tuyến và do đó, không yêu cầu thêm mảng và biến tạm thời để lưu trữ giá trị

Một ví dụ về Shell Sort. Giả sử chúng ta có một ARRAY = [34, 32, 41, 9, 13, 18, 26, 43]

• Đối với bộ so sánh đầu tiên, khoảng cách sẽ là kích thước [ARRAY]/2 i. e. 8/2 = 4 quãng
• So sánh tập hợp con = {34,13}, {32,18}, {41,26}, {9,43}
• Sau khi hoán đổi các tập hợp con, giá trị nhỏ ở bên trái và giá trị lớn ở bên phải
• Các tập con sau khi đổi chỗ = {13,34}, {18,32}, {26,41}, {9,43}
• ARRAY sẽ là sau khi hoán đổi = [13, 18, 26, 9, 34, 32, 41, 43]
• Đối với tập so sánh thứ hai, chúng tôi sẽ tạo tập hợp con cho 2 khoảng thời gian và nó sẽ cung cấp 2 danh sách phụ {13, 26, 34, 41}, {18, 9, 32, 43}
• Khi có khoảng 1 với khoảng cách 1, chúng ta sẽ áp dụng sắp xếp chèn trên mảng

Thuận lợi

• Với độ phức tạp thời gian trung bình được cải thiện, đây là một thuật toán rất hiệu quả cho các mảng kích thước trung bình
• Nó tốt hơn sắp xếp Chèn và nhanh hơn 5 lần so với sắp xếp Bong bóng

Nhược điểm

• Đó là một thuật toán phức tạp
• Không hiệu quả như sắp xếp hợp nhất và sắp xếp nhanh
• Bị giới hạn sử dụng cho các mảng kích thước nhỏ vì hiệu suất giảm khi kích thước mảng tăng

Triển khai bằng Python

def shellSort[alist]:
    sublistcount = len[alist]//2
    while sublistcount > 0:

      for startposition in range[sublistcount]:
        gapInsertionSort[alist,startposition,sublistcount]

      print["After increments of size",sublistcount,
                                   "The list is",alist]

      sublistcount = sublistcount // 2

def gapInsertionSort[alist,start,gap]:
    for i in range[start+gap,len[alist],gap]:

        currentvalue = alist[i]
        position = i

        while position>=gap and alist[position-gap]>currentvalue:
            alist[position]=alist[position-gap]
            position = position-gap

        alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
shellSort[alist]
print[alist]

đầu ra

After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77]
After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93]
After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]

Triển khai trong C++

#include
#include 

void shell_sort[int arr[],int n]
{ 
   int temp;
   for[int gap=n/2;gap>0;gap/=2]
   {
     for[int i=gap;i=gap && arr[j-gap]>temp; j-=gap]
          {
              arr[j]=arr[j-gap];
          }
         arr[j]=temp;
        }
      }
    }

void main[]
{
    clrscr[];
    int len, arr[100];

    coutlen;

    for[int i=0;i>arr[i];
    }

    shell_sort[arr,len];

    cout