Insertion sort là gì? Thuật toán sắp xếp chèn Insertion sort trong C/C++

Insertion sort là một thuật ngữ được sử dụng phổ biến trong lập trình. Bài viết này sẽ giúp bạn tìm hiểu về khái niệm cũng như thuật toán của Insertion sort trong C++ nhé

I. Sắp xếp chèn – Insertion sort là gì?

1. Khái niệm

Insertion sort hay còn được gọi là thuật toán sắp xếp chèn với cách thức hoạt động có phần tương đồng với thuật toán sắp xếp nổi bọt.

Thuật toán sắp xếp chèn sẽ lần lượt chọn giá trị của các phần tử trong mảng (từ giá trị thứ 2 đến giá trị cuối cùng) và so sánh với với các giá trị phía trước vị trí của nó. Nếu tìm được vị trí phù hợp, phần tử ấy sẽ được chèn vào vị trí thích hợp giữa các giá trị trước nhưng vẫn đảm bảo mảng được sắp xếp theo thứ tự.

Ví dụ về thuật toán sắp xếp chèn Insertion Sort trong C/C++

2. Ý tưởng

Với thuật toán sắp xếp chèn, ta chia mảng thành các phần sau:

Mảng a (Mảng đã sắp xếp): Bắt đầu từ a[0] đến a[i – 1], lưu các phần tử trong mảng đã được sắp xếp theo thứ tự.
Mảng a’ (Mảng chưa sắp xếp): Bắt đầu từ a[i] đến a[n – 1], lưu các giá trị đang được sắp xếp.

Thuật toán sắp xếp sẽ lần lượt so sánh từng phần tử a[i] trong mảng a’ (mảng chưa sắp xếp) trong mảng đợi với các giá trị trong mảng a (mảng đã sắp xếp) theo thứ tự từ phải qua trái (từ a[i-1] đến a[0]). Gọi a[j] là phần tử trong mảng a và j = i – 1.

Nếu a[i] chưa thỏa điều kiện đúng theo thứ tự sắp xếp trong mảng a thì:

Dịch chuyển giá trị của a[j] sang vị trí a[j+1].
Lùi j xuống 1 đơn vị (j-1)
Tiếp tục so sánh a[i] với a[j] và liên tục thực hiện so sánh cho đến khi a[i] thỏa đúng hoặc đã vét cạn mảng a

Nếu a[i] thỏa điều kiện đúng theo thứ tự sắp xếp trong mảng a:

Dừng việc so sánh a[i] và mảng a.
Chèn a[i] vào vị trí a[j+1] để mảng a đúng thứ tự.

Ý tưởng thuật toán sắp xếp chèn – Insertion Sort

3. Giải thuật

Bước 1: Giả định a[0] là một mảng đã được sắp xếp theo thứ tự.

Bước 2: So sánh a[1] với a[0] và sắp xếp lại sao cho mảng đã sắp xếp gồm a[0] và a[1] được sắp thứ tự.

Bước 3: So sánh a[2] với a[0] và a[1], sau đó sắp xếp lại sao cho mảng đã sắp xếp gồm a[0], a[1], a[2] được sắp xếp thứ tự.

Bước i: So sánh a[i] với các giá trị trong mảng đã sắp xếp từ a[i-1] lùi xuống a[0], sau đó sắp xếp lại sao cho mảng đã sắp xếp từ a[0] đến a[ơi] được sắp xếp thứ tự. Thực hiện liên tục như vậy cho đến hết mảng.

Bước cuối: Sau khi sắp xếp theo thứ tự xong, ta xuất mảng.

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

II. Cách viết thuật toán sắp xếp chèn – Insertion Sort

1. Code minh họa

2. Gợi ý

Khởi tạo hàm InsertionSort() để sắp xếp vị trí.
Dùng biến “l” để lưu tạm giá trị a[i] để khi sắp xếp xong thì giá trị không bị mất đi.
Dùng vòng lặp While để có thể chạy lùi mảng con từ a[i-1] về a[0].
Tạo hàm printArray() để in mảng sau khi sắp xếp.