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

Chấn Phong

Sắp xếp chèn (Insertion Sort) là gì?

Sắp xếp chèn là một giải thuật sắp xếp dựa trên so sánh in-place. Ở đây, một danh sách con luôn luôn được duy trì dưới dạng đã qua sắp xếp. Sắp xếp chèn là chèn thêm một phần tử vào danh sách con đã qua sắp xếp. Phần tử được chèn vào vị trí thích hợp sao cho vẫn đảm bảo rằng danh sách con đó vẫn sắp theo thứ tự.

Với cấu trúc dữ liệu mảng, chúng ta tưởng tượng là: mảng gồm hai phần: một danh sách con đã được sắp xếp và phần khác là các phần tử không có thứ tự. Giải thuật sắp xếp chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, và các phần tử không có thứ tự sẽ được di chuyển và được chèn vào vị trí thích hợp trong danh sách con (của cùng mảng đó).

Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.

Cách giải thuật sắp xếp chèn thực hiện?

Ví dụ chúng ta có một mảng gồm các phần tử không có thứ tự:

Sắp xếp chèn (Insertion Sort)

Giải thuật sắp xếp chèn so sánh hai phần tử đầu tiên:

Sắp xếp chèn (Insertion Sort)

Giải thuật tìm ra rằng cả 14 và 33 đều đã trong thứ tự tăng dần. Bây giờ, 14 là trong danh sách con đã qua sắp xếp.

Sắp xếp chèn (Insertion Sort)

Giải thuật sắp xếp chèn tiếp tục di chuyển tới phần tử kế tiếp và so sánh 33 và 27.

Sắp xếp chèn (Insertion Sort)

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

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

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.

Giải thuật sắp xếp chèn tráo đổi vị trí của 33 và 27

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.

Tiếp tục so sánh 33 với 10

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

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

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

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ự.

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.

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ự.

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ử.

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