Các thuật toán sắp xếp đơn giản
Tóm tắt
Bài học giới thiệu ý tưởng sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt.
Hiểu bài
Sắp xếp chèn cho chỉ số i chạy từ phần tử thứ hai đến cuối dãy và chèn A[i] vào đúng vị trí trong dãy con đã sắp xếp bên trái. Sắp xếp chọn, tại mỗi vị trí i, tìm phần tử nhỏ nhất trong đoạn chưa sắp xếp rồi đổi chỗ với A[i]. Với dãy 5, 3, 9, 7, 2, các lượt chọn đưa dãy qua 2, 3, 9, 7, 5, rồi 2, 3, 5, 7, 9. Sắp xếp nổi bọt so sánh các cặp kề nhau; nếu A[j] > A[j+1] thì đổi chỗ. Sau mỗi vòng, một phần tử lớn được đưa về cuối.
Các vòng lặp của thuật toán sắp xếp chọn SGK trang 102