1. Kiến thức trọng tâm
Sắp xếp là việc sắp xếp lại các phần tử của dãy theo thứ tự tăng dần hoặc giảm dần. Sắp xếp quan trọng vì nhiều thuật toán khác, như tìm kiếm nhị phân, yêu cầu dữ liệu đã sắp xếp. Trong thực tế, sắp xếp xuất hiện ở khắp nơi: xếp hạng học sinh theo điểm, sắp xếp hàng hóa theo giá, sắp xếp tên trong danh bạ.
Hai thuật toán sắp xếp đơn giản là sắp xếp nổi bọt và sắp xếp chọn. Sắp xếp nổi bọt lặp lại việc so sánh từng cặp kề nhau và đổi chỗ nếu sai thứ tự. Sau mỗi lượt duyệt, phần tử lớn nhất sẽ "nổi" lên cuối dãy, giống như bọt khí nổi lên mặt nước. Quá trình lặp lại cho đến khi dãy được sắp xếp hoàn toàn.
Sắp xếp chọn hoạt động theo cách khác: ở mỗi bước, thuật toán tìm phần tử nhỏ nhất trong phần chưa sắp xếp rồi đổi chỗ nó với phần tử đầu tiên của phần chưa sắp xếp. Sau mỗi bước, phần đã sắp xếp dài thêm một phần tử. Cả hai thuật toán đều dễ hiểu, dễ cài đặt nhưng chạy chậm khi dãy dài, nên chỉ phù hợp với dãy ít phần tử hoặc dùng để học tập.
2. Ví dụ minh họa
Ví dụ: sắp xếp dãy 5, 2, 8, 1 tăng dần bằng sắp xếp nổi bọt. Lượt 1: so sánh 5 và 2, đổi chỗ được 2, 5, 8, 1; so sánh 5 và 8, giữ nguyên; so sánh 8 và 1, đổi chỗ được 2, 5, 1, 8; 8 đã về đúng vị trí cuối. Lượt 2: so sánh 2 và 5, giữ nguyên; so sánh 5 và 1, đổi chỗ được 2, 1, 5, 8; 5 đã về đúng vị trí. Lượt 3: so sánh 2 và 1, đổi chỗ được 1, 2, 5, 8; dãy đã sắp xếp hoàn toàn.
3. Ghi nhớ
- Sắp xếp là việc sắp xếp lại các phần tử theo thứ tự tăng dần hoặc giảm dần.
- Sắp xếp nổi bọt: so sánh từng cặp kề nhau và đổi chỗ nếu sai thứ tự.
- Sắp xếp chọn: mỗi bước chọn phần tử nhỏ nhất trong phần chưa sắp xếp đưa lên đầu.
- Hai thuật toán đơn giản, dễ hiểu, nhưng chạy chậm với dãy dài.