Trong bài viết này, chúng ta sẽ tìm hiểu về thuật toán sắp xếp chèn (Insertion Sort) trong C / C++, một thuật toán nhanh hơn và tối ưu hơn thuật toán sắp xếp nổi bọt (Bubble Sort).
Sắp xếp chèn là gì? Hoạt động như thế nào
Thuật toán sắp xếp chèn duyệt từng phần tử trong mảng, so sánh và chèn vào mảng sao cho đúng thứ tự. Về cơ bản, nó hoạt động như việc bạn sắp xếp một bài hát theo thứ tự nhạc phẩm trên một playlist.
Ví dụ trên đây minh họa quá trình sắp xếp chèn. Ban đầu, nó so sánh cặp số 4 và 3. Vì 3 nhỏ hơn 4, nên nó chèn số 3 vào trước số 4. Tiếp theo, cặp 4 và 2, vì 2 nhỏ hơn 4 và 3, nên nó chèn số 2 vào trước số 3. Quá trình này tiếp tục cho đến khi mảng được sắp xếp hoàn chỉnh.
Mặc dù thuật toán sắp xếp chèn nhanh hơn thuật toán sắp xếp nổi bọt, nhưng vẫn chưa được tối ưu vì cần duyệt hết tất cả các phần tử trong mảng.
Nếu bạn mới bắt đầu học lập trình, hãy tìm hiểu thuật toán này, vì nó cơ bản và không quá phức tạp. Bạn cũng có thể tìm hiểu những thuật toán sắp xếp khác tối ưu hơn trong các bài viết tiếp theo.
Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++
Đối với thuật toán sắp xếp chèn (Insertion Sort) trong C / C++, chúng ta không cần sử dụng hàm Swap() để hoán đổi vị trí giữa hai phần tử. Dưới đây là mã nguồn của thuật toán sắp xếp chèn, được giải thích chi tiết trong phần tiếp theo.
Giải thích thuật toán:
- Đầu tiên, kiểm tra xem phần tử đầu tiên đã được sắp xếp chưa. Nếu đã sắp xếp, trả về 1.
- Lấy phần tử tiếp theo để so sánh với các phần tử trong mảng đã sắp xếp.
- Di chuyển các phần tử trong mảng đã sắp xếp nếu nó lớn hơn giá trị đó.
- Sau khi di chuyển, chèn phần tử đó vào đúng vị trí.
- Tiếp tục lặp lại cho đến khi hết mảng.
Dưới đây là một ví dụ sử dụng thuật toán sắp xếp chèn (Insertion Sort) trong C / C++.
Đề bài: Viết chương trình sắp xếp các phần tử trong mảng được nhập bởi người dùng. Số lượng phần tử trong mảng không được nhỏ hơn 0, nếu nhỏ hơn, yêu cầu nhập lại. Sử dụng thuật toán sắp xếp chèn để sắp xếp các phần tử.
Gợi ý:
- Đầu tiên, viết hàm insertionSort() để sắp xếp các phần tử trong mảng được truyền vào.
- Tạo hàm printArray() để xuất các phần tử trong mảng được truyền vào.
- Yêu cầu người dùng nhập các phần tử trong mảng, sau đó gọi hàm insertionSort() để sắp xếp.
- Cuối cùng, gọi hàm printArray() để xuất các phần tử trong mảng sau khi sắp xếp.
Dưới đây là hai chương trình viết bằng ngôn ngữ C và C++. Bạn có thể tham khảo nhé.
Chương trình C:
Kết quả:Chương trình C++:
Kết quả:Như vậy là chúng ta đã tìm hiểu về thuật toán sắp xếp chèn (Insertion Sort) trong C / C++. Trong bài viết tiếp theo, chúng ta sẽ giới thiệu thuật toán sắp xếp chọn (Selection Sort) trong C / C++. Hãy tiếp tục theo dõi nhé!