Bài 49. Thuật toán sắp xếp chèn (Insertion sort)

thuật toán insertion sort minh họa code c++
thuật toán insertion sort minh họa code c++

Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++.

Ở bài viết này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp chèn. Nội dung bài viết bao gồm các phần sau:

  • Ý tưởng của thuật toán
  • Ví dụ minh họa
  • Minh họa thuật toán sử dụng ngôn ngữ C++
  • Đánh giá thuật toán

Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu

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

Minh họa thuật toán sắp xếp chèn
Minh họa thuật toán sắp xếp chèn

Thuật toán sắp xếp chèn thực hiện sắp xếp dãy số theo cách duyệt từng phần tử và chèn từng phần tử đó vào đúng vị trí trong mảng con(dãy số từ đầu đến phần tử phía trước nó) đã sắp xếp sao cho dãy số trong mảng sắp đã xếp đó vẫn đảm bảo tính chất của một dãy số tăng dần.

  1. Khởi tạo mảng với dãy con đã sắp xếp có k = 1 phần tử(phần tử đầu tiên, phần tử có chỉ số 0)
  2. Duyệt từng phần tử từ phần tử thứ 2, tại mỗi lần duyệt phần tử ở chỉ số i thì đặt phần tử đó vào một vị trí nào đó trong đoạn từ [0…i] sao cho dãy số từ [0…i] vẫn đảm bảo tính chất dãy số tăng dần. Sau mỗi lần duyệt, số phần tử đã được sắp xếp k trong mảng tăng thêm 1 phần tử.
  3. Lặp cho tới khi duyệt hết tất cả các phần tử của mảng.

Ví dụ minh họa

Một ví dụ minh họa thuật toán insertion sort
Một ví dụ minh họa thuật toán sắp xếp chèn

Hàng đầu tiên mô phỏng trạng thái ban đầu của mảng(dãy số chưa sắp xếp). Từ hàng thứ 2 trở đi, ta tìm chèn số đang xét vào vị trí thích hợp để đảm bảo dãy số vẫn tăng dần. Và khi lặp hết tất cả các số trong mảng, ta có trạng thái đã sắp xếp ở hàng cuối cùng.

Minh họa thuật toán sử dụng ngôn ngữ C++

Kết quả chạy thử chương trình:

Đánh giá thuật toán sắp xếp chèn

Độ  phức tạp thuật toán

  • Trường hợp tốt: O(n)
  • Trung bình: O(n^2)
  • Trường hợp xấu: O(n^2)

Không gian bộ nhớ sử dụng: O(1)

Nếu thấy bài viết hay và bổ ích, hay like và follow fanpage Học lập trình cùng Nguyễn Văn Hiếu để nhận thông báo về những bài viết mới nhất nhé.

avatar
  Subscribe  
Notify of