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ì và 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ử sẽ được 'chèn' vào danh sách con đượ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,insertion sort.

Mảng được tìm kiếm tuần tự và các mục chưa được sắp xếp được di chuyển và chèn vào danh sách con đã 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ặt hàng.

Cách sắp xếp chèn hoạt động?

Chúng tôi lấy một mảng không được sắp xếp để làm ví dụ.

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

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

Sắp xếp chèn di chuyển lên 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 với tất cả các phần tử của danh sách con được sắp xếp. Ở đây chúng ta thấy rằng danh sách con đã sắp xếp chỉ có một phần tử 14 và 27 lớn hơn 14. Do đó, danh sách con đã sắp xếp vẫn được sắp xếp sau khi hoán đổi.

Bây giờ chúng ta có 14 và 27 trong danh sách phụ đã 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 hoán đổi chúng.

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

Do đó, chúng tôi cũng hoán đổi chúng.

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

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

Quá trình này tiếp tục 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 con đượ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 toàn cảnh hơn về cách thức hoạt động của kỹ thuật sắp xếp này, vì vậy chúng ta có thể rút ra các bước đơn giản mà 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

Để biết về triển khai sắp xếp chèn trong ngôn ngữ lập trình C, vui lòng nhấp vào đây .