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é

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

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

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

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.

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

Code minh họa

Code: Thuật toán sắp xếp chèn insertion sort

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.

Xem thêm:

• Kotlin là gì? So sánh ngôn ngữ lập trình Kotlin và Java
• Python là gì? Vì sao nên học lập trình Python?
• Mô hình erd là gì? Cách chuyển mô hình erd sang mô hình quan hệ

Hy vọng bài viết này sẽ giúp bạn làm chủ được Insertion sort để ứng dụng vào công việc một cách hiệu quả nhất nhé. Chúc các bạn thực hiện thành công!