Sắp xếp chèn - Insertion Sort (Cấu trúc dữ liệu và giải thuật)

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

Với cấu trúc dữ liệu mảng, chúng ta cần tưởng tượng là: mảng gồm có 2 phần: một danh sách con đã được sắp xếp và một phần khác là những phần tử không có thứ tự. Giải thuật sắp xếp chèn sẽ thực hiện công việc tìm kiếm liên tiếp thông qua mảng đó, và những phần tử không có thứ tự sẽ được di chuyển và được chèn vào một 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 những 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à Ο (n²) trong đó 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 những phần tử không sắp xếp theo thứ tự:

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

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

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

Và thấy rằng 33 chưa nằm đúng vị trí.

Giải thuật sắp xếp chèn sẽ tráo đổi vị trí của hai phần tử 33 và 27. Đồng thời cũng kiểm tra những phần tử trong danh sách con đã sắp xếp. Tại đây, chúng ta có thể 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. Vậy nên danh sách con vẫn được giữ nguyên sau khi đã tráo đổi.

Bây giờ trong danh sách con của chúng ta có 2 giá trị 14 và 27. Tiếp tục so sánh 33 với phần tử tiếp theo là 10.

Hai giá trị này chưa sắp xếp đúng theo thứ tự.

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

Việc tráo đổi dẫn tới 27 và 10 chưa theo thứ tự.

Vì thế chúng ta cần phải tráo đổi chúng.

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

Và chúng ta tiếp tục tráo đổi 2 phần tử 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 lặp lại cho đến khi tất cả các giá trị chưa được sắp xếp đúng được sắp xếp đúng vào trong danh sách con đã qua sắp xếp.

Sau đây chúng ta sẽ 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ừ ví dụ minh họa ở trên chúng ta đã có một bức tranh tổng quát về giải thuật sắp xếp chèn, từ đó chúng ta sẽ có những bước cơ bản trong giải thuật như dưới đây:

Bước 1: Kiểm tra nếu phần tử đầu tiên đã được sắp xếp xong. trả về 1 Bước 2: Lấy phần tử tiếp theo Bước 3: So sánh với tất cả các phần tử trong danh sách con đã qua sắp xếp Bước 4: Dịch chuyển tất cả các phần tử trong danh sách con có giá trị lớn hơn để được sắp xếp Bước 5: Chèn giá trị đó Bước 6: Lặp lại cho đến 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 Bài trước: Sắp xếp nổi bọt - Bubble Sort (Cấu trúc dữ liệu và giải thuật)