Giải thuật sắp xếp chèn (Insertion Sort)

Giải thuật sắp xếp chèn tráo đổi vị trí của 33 và 27. Đồng thời cũng kiểm tra tất cả phần tử trong danh sách con đã sắp xếp. Tại đây, chúng ta thấy rằng trong danh sách con này chỉ có một phần tử 14 và 27 là lớn hơn 14. Do vậy danh sách con vẫn giữ nguyên sau khi đã tráo đổi.

Bây giờ trong danh sách con chúng ta có hai giá trị 14 và 27. Tiếp tục so sánh 33 với 10.

Hai giá trị này không theo thứ tự.

Vì thế chúng ta tráo đổi chúng.

Việc tráo đổi dẫn đến 27 và 10 không theo thứ tự.

Vì thế chúng ta cũng tráo đổi chúng.

Chúng ta lại thấy rằng 14 và 10 không theo thứ tự.

Và chúng ta tiếp tục tráo đổi hai số này. Cuối cùng, sau vòng lặp thứ 3 chúng ta có 4 phần tử.

Tiến trình trên sẽ tiếp tục diễn ra cho tới khi tất cả giá trị chưa được sắp xếp được sắp xếp hết vào trong danh sách con đã qua sắp xếp.

Tiếp theo chúng ta cùng tìm hiểu khía cạnh lập trình của giải thuật sắp xếp chèn.

Giải thuật sắp xếp chèn (Insertion Sort)

Từ minh họa trên chúng ta đã có bức tranh tổng quát về giải thuật sắp xếp chèn, từ đó chúng ta sẽ có các bước cơ bản trong giải thuật như sau:

Bước 1: Kiểm tra nếu phần tử đầu tiên đã được sắp xếp. trả về 1
Bước 2: Lấy phần tử kế tiếp
Bước 3: So sánh với tất cả phần tử trong danh sách con đã qua sắp xếp
Bước 4: Dịch chuyển tất cả phần tử trong danh sách con mà lớn hơn giá trị để được sắp xếp
Bước 5: Chèn giá trị đó
Bước 6: Lặp lại cho tới khi danh sách được sắp xếp

Giải thuật mẫu cho sắp xếp nổi bọt

Bắt đầu hàm insertionSort( A : mảng phần tử )
   int holePosition
   int valueToInsert
	
   for i = 1 tới length(A) thực hiện:
	
      /* chọn một giá trị để chèn */
      valueToInsert = A[i]
      holePosition = i
      
      /*xác định vị trí cho phần tử được chèn */
		
      while holePosition > 0 và A[holePosition-1] > valueToInsert thực hiện:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      kết thúc while
		
      /* chèn giá trị tại vị trí trên */
      A[holePosition] = valueToInsert
      
   kết thúc for
	
Kết thúc hàm

Theo Tutorialspoint

Bài trước: Giải thuật sắp xếp nổi bọt (Bubble Sort)

Bài tiếp: Giải thuật sắp xếp chọn (Selection Sort)