/codegym.vn/ - 152
Chương 8 - Thuật toán sắp xếp
Sắp xếp được dữ liệu theo các trật tự và tiêu chí khác nhau
1. Mục tiêu
● Liệt kê được các trường hợp áp dụng của thuật toán sắp xếp
● Trình bày được thuật toán sắp xếp Nổi bọt
● Cài đặt được thuật toán sắp xếp Nổi bọt
● Trình bày được thuật toán sắp xếp Chọn
● Cài đặt được thuật toán sắp xếp Chọn
● Trình bày được thuật toán sắp xếp Chèn
● Cài đặt được thuật toán sắp xếp Chèn
● Phân biệt được độ phức tạp của các thuật toán sắp xếp để có lựa chọn phù
hợp
2. Giới thiệu
Sắp xếp là thao tác thay đổi vị trí của các phần tử trong một danh sách để thoả mãn
một tiêu chí nhất định. Chúng ta thường gặp các danh sách có trật tự, chẳng hạn danh
sách thí sinh dự thi trong một kỳ thi Đại học được sắp xếp theo tên, danh sách các
quốc gia theo độ lớn của diện tích, danh sách khách hàng theo tổng giá trị hợp đồng,
v.v. Để thực hiện được thao tác thay đổi vị trí của các phần tử một cách hiệu quả,
chúng ta sẽ cần nghiên cứu nhiều thuật toán sắp xếp khác nhau.
Độ phức tạp của một thuật toán sắp xếp phụ thuộc vào số lượng phép so sánh và số
lượng phép hoán vị cần phải thực hiện. Tối ưu hóa hai đại lượng này chính là mục
tiêu của các thuật toán sắp xếp. Có nhiều thuật toán sắp xếp khác nhau, tùy thuộc
vào kích thước và cách phân phối của các phần tử trong danh sách đầu vào mà mỗi
loại thuật toán thể hiện một ưu thế riêng.
Kết thúc chương này, chúng ta có thể lựa chọn triển khai một số thuật toán sắp xếp
khác nhau để phù hợp với các tình huống cụ thể. Chúng ta sẽ khảo sát 3 thuật toán
cơ bản bao gồm: Sắp xếp Nổi bọt, Sắp xếp Chèn, Sắp xếp Chọn.
3. Thuật toán sắp xếp nổi bọt
Sắp xếp nổi bọt (bubble sort) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản
là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap)
cho nhau, việc đổi chỗ này được lặp đi lặp lại cho đến khi không còn phần tử nào
đứng không đúng thứ tự.
