Exchange sort là gì

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 seriescác thuật toán sắp xếpcó minh họa code sử dụng ngôn ngữ lập trình C++.

Ở bài viết nàyNguyễn Văn Hiếuxin giới thiệu tới các bạn thuật toán sắp xếp bubble sort. 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 của thuật toán bubble sort

Thuật toán sắp xếp bubble sort thứcj hiện sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự[số sau bé hơn số trước với trường hợp sắp xếp tăng dần] cho đến khi dãy số được sắp xếp.

Ví dụ minh họa

Giả sử chúng ta cần sắp xếp dãy số [514 2 8] này tăng dần.
Lần lặp đầu tiên:
[514 2 8 ] > [154 2 8 ], Ở đây, thuật toán sẽ so sánh hai phần tử đầu tiên, và đổi chỗ cho nhau do 5 > 1.
[ 1542 8 ] > [ 1452 8 ], Đổi chỗ do 5 > 4
[ 1 4528 ] > [ 1 4258 ], Đổi chỗ do 5 > 2
[ 1 4 258] > [ 1 4 258], Ở đây, hai phần tử đang xét đã đúng thứ tự [8 > 5], vậy ta không cần đổi chỗ.

Lần lặp thứ 2:
[142 5 8 ] > [142 5 8 ]
[ 1425 8 ] > [ 1245 8 ], Đổi chỗ do 4 > 2
[ 1 2458 ] > [ 1 2458 ]
[ 1 2 458] > [ 1 2 458]
Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện.

Lần lặp thứ 3:
[124 5 8 ] > [124 5 8 ]
[ 1245 8 ] > [ 1245 8 ]
[ 1 2458 ] > [ 1 2458 ]
[ 1 2 458] > [ 1 2 458]

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