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

Lập trìnhInsertion sort là gì? Thuật toán sắp xếp chèn Insertion sort trong...

Ngày đăng:

0
(0)

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

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

Ý 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
Ý tưởng thuật toán sắp xếp chèn – Insertion Sort

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
Giải thuật sắp xếp chèn – Insertion Sort

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.
Kết quả
Kết quả

Xem thêm:

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!

Bạn thấy bài viết này hữu ích chứ?

Hãy chọn vào ngôi sao để đánh giá bài viết

Đánh giá trung bình 0 / 5. Lượt đánh giá 0

Hãy là người đầu tiên đánh giá bài viết

Hãy để lại bình luận

Xem nhiều

Bài tin liên quan

1km2 bằng bao nhiêu hm2? Quy đổi Kilômét vuông sang Héctômét vuông

Ki-lô-mét vuông và héc-tô-mét vuông là đơn vị đo...

Kg/cm2 là gì? Quy đổi kg/cm2 sang kN/m2, MPa, t/m2, psi, kPa, bar

Các đơn vị đo áp suất thường được ứng...

1 hg bằng bao nhiêu kg? Quy đổi từ Héctôgam sang Kilôgam

Đơn vị đo khối lượng hg và kg không...

1kg bằng bao nhiêu tạ, gam, tấn, yến? Cách đổi đơn vị kilogam

Trong cân lường, đơn vị ki-lô-gam thường được chuyển...