Cộng đồng chia sẻ tri thức Lib24.vn

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

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 11:32:12


Mục lục
* * * * *

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 các dịch chuyển lớn như trong trường hợp sắp xếp chèn, nếu giá trị nhỏ hơn nằm ở bên phải và phải được chuyển sang bên trái.

Thuật toán này sử dụng sắp xếp chèn trên một phần tử trải rộng, 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 rộng rãi hơn. Khoảng cách này được gọi là khoảng . Khoảng 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 cách được biết đến nhiều nhất là Ο (n), trong đó n là số lượng mục. Và độ phức tạp không gian trường hợp xấu nhất là O (n).

Shell sắp xếp hoạt động như thế nào?

Chúng ta hãy xem xét ví dụ sau đây để có một ý tưởng về cách sắp xếp shell hoạt động. 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 đây của chúng tôi. Để có ví dụ và dễ hiểu, chúng tôi lấy khoảng 4. Tạo một danh sách phụ ảo của tất cả các giá trị nằm ở khoảng của 4 vị trí. Ở đây các giá trị này là {35, 14}, {33, 19}, {42, 27} và {10, 44}

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

Chúng tôi so sánh các giá trị trong mỗi danh sách phụ và trao đổ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 -

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

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

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

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

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

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

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

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

Chúng tôi thấy rằng nó 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 shell.

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 sắp xếp vỏ.

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

Được cập nhật: 25 tháng 3 lúc 12:56:35 | Lượt xem: 609