Cấu trúc dữ liệu và thuật toán - Sắp xếp hệ vỏ

Shell sort là một thuật toán sắp xếp hiệu quả cao và dựa trên thuật toán sắp xếp chèn. Thuật toán này tránh sự thay đổi lớn như trong trường hợp sắp xếp chèn, nếu giá trị nhỏ hơn ở ngoài cùng bên phải và phải được di chuyển sang ngoài cùng bên trái.

Thuật toán này sử dụng sắp xếp chèn trên các phần tử phổ biến rộng rãi, trước tiên để sắp xếp chúng và sau đó sắp xếp các phần tử có khoảng cách ít hơn. Khoảng cách này được gọi làinterval. Khoảng thời gian này được tính dựa trên công thức của Knuth là:

Công thức của Knuth

h = h * 3 + 1
where −
   h is interval with initial value 1

Thuật toán này khá hiệu quả đối với các tập dữ liệu cỡ trung bình vì độ phức tạp trung bình và trường hợp xấu nhất của thuật toán này phụ thuộc vào chuỗi khoảng trống được biết đến nhiều nhất là Ο (n), trong đó n là số mục. Và độ phức tạp không gian trong trường hợp xấu nhất là O (n).

Shell Sort hoạt động như thế nào?

Chúng ta hãy xem xét ví dụ sau để có ý tưởng về cách hoạt động của shell sort. Chúng tôi lấy cùng một mảng mà chúng tôi đã sử dụng trong các ví dụ trước của chúng tôi. Để làm ví dụ và dễ hiểu, chúng ta lấy khoảng 4. Tạo một danh sách con ảo gồm tất cả các giá trị nằm trong khoảng 4 vị trí. Ở đây các giá trị này là {35, 14}, {33, 19}, {42, 27} và {10, 44}

Chúng tôi so sánh các giá trị trong mỗi danh sách con và hoán đổi chúng (nếu cần) trong mảng ban đầu. Sau bước này, mảng mới sẽ trông như thế này -

Sau đó, chúng tôi lấy khoảng 1 và khoảng cách này tạo ra hai danh sách con - {14, 27, 35, 42}, {19, 10, 33, 44}

Chúng tôi so sánh và hoán đổi các giá trị, nếu cần, trong mảng ban đầu. Sau bước này, mảng sẽ giống như sau:

Cuối cùng, chúng tôi sắp xếp phần còn lại của mảng bằng cách sử dụng khoảng giá trị 1. Shell sắp xếp sử dụng sắp xếp chèn để sắp xếp mảng.

Sau đây là mô tả từng bước -

Chúng ta thấy rằng chỉ cần bốn lần hoán đổi để sắp xếp phần còn lại của mảng.

Thuật toán

Sau đây là thuật toán sắp xếp trình bao.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

Mã giả

Sau đây là mã giả cho loại trình bao.

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

Để biết cách triển khai shell sort trong ngôn ngữ lập trình C, vui lòng nhấp vào đây .