Cấu trúc dữ liệu và thuật toán sắp xếp chèn

Đây là một thuật toán sắp xếp dựa trên so sánh tại chỗ. Ở đây, một danh sách phụ được duy trì luôn được sắp xếp. Ví dụ, phần dưới của một mảng được duy trì để được sắp xếp. Một phần tử được 'chèn' trong danh sách phụ được sắp xếp này, phải tìm vị trí thích hợp của nó và sau đó nó phải được chèn vào đó. Do đó tên, chèn sắp xếp .

Mảng được tìm kiếm tuần tự và các mục chưa sắp xếp được di chuyển và chèn vào danh sách phụ được sắp xếp (trong cùng một mảng). Thuật toán này không phù hợp với các tập dữ liệu lớn vì độ phức tạp trung bình và trường hợp xấu nhất của nó là Ο (n ² ), trong đó n là số lượng mục.

Sắp xếp chèn hoạt động như thế nào?

Chúng tôi lấy một mảng chưa sắp xếp cho ví dụ của chúng tôi.

Sắp xếp chèn so sánh hai yếu tố đầu tiên.

Nó thấy rằng cả 14 và 33 đã theo thứ tự tăng dần. Hiện tại, 14 là trong danh sách phụ được sắp xếp.

Sắp xếp chèn di chuyển về phía trước và so sánh 33 với 27.

Và thấy rằng 33 không đúng vị trí.

Nó hoán đổi 33 với 27. Nó cũng kiểm tra tất cả các yếu tố của danh sách phụ được sắp xếp. Ở đây chúng ta thấy rằng danh sách phụ được sắp xếp chỉ có một phần tử 14 và 27 lớn hơn 14. Do đó, danh sách phụ được sắp xếp vẫn được sắp xếp sau khi hoán đổi.

Đến bây giờ chúng ta có 14 và 27 trong danh sách phụ được sắp xếp. Tiếp theo, nó so sánh 33 với 10.

Các giá trị này không theo thứ tự được sắp xếp.

Vì vậy, chúng tôi trao đổi chúng.

Tuy nhiên, trao đổi làm cho 27 và 10 không được sắp xếp.

Do đó, chúng tôi trao đổi chúng quá.

Một lần nữa chúng tôi tìm thấy 14 và 10 theo thứ tự chưa được sắp xếp.

Chúng tôi trao đổi chúng một lần nữa. Đến cuối lần lặp thứ ba, chúng tôi có một danh sách phụ được sắp xếp gồm 4 mục.

Quá trình này diễn ra cho đến khi tất cả các giá trị chưa được sắp xếp được bao phủ trong một danh sách phụ được sắp xếp. Bây giờ chúng ta sẽ thấy một số khía cạnh lập trình của sắp xếp chèn.

Thuật toán

Bây giờ chúng ta có một bức tranh lớn hơn về cách thức kỹ thuật sắp xếp này hoạt động, vì vậy chúng ta có thể rút ra các bước đơn giản để chúng ta có thể đạt được sắp xếp chèn.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Mã giả

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

Được cập nhật: 17 tháng 4 lúc 10:12:42 | Lượt xem: 538