CẤU TRÚC DỮ LIỆU VÀ
GIẢI THUẬT
NGÔ QUANG THẠCH
Email: thachnq@gmail.com
ĐT: 01273984123
Chương 4: Các phương pháp sắp xếp cơ bản
Định nghĩa bài toán sắp xếp
Phương pháp chọn (Selection sort)
Phương pháp chèn (Insertion sort)
Phương pháp đổi chỗ (Interchange sort)
Phương pháp nổi bọt (Bubble sort)
Phương pháp sắp xếp nhanh (Quick sort)
Định nghĩa bài toán sắp xếp
Phát biểu bài toán:
- Cho tập n đối tượng (phần tử).
- Hãy sắp xếp n đối tượng trên theo thứ tự tăng (giảm)
Tổ chức dữ liệu
- int n Số phần tử cần sắp xếp
- int A[n] Lưu trữ tập hợp n phần tử
Định nghĩa bài toán sắp xếp
Sắp xếp là một quá trình xử lý bố trí lại một danh sách
các đối tượng theo thứ tự nào đó.
Ví dụ: Cần sắp xếp danh sách thí sinh theo tên với thứ
tự Alphabet, hoặc sắp xếp danh sách sinh viên theo
điểm trung bình với thứ tự từ cao đến thấp.
Các đối tượng cần được sắp xếp thường có nhiều thuộc
tính chúng ta cần chọn một thuộc tính làm khóa và sắp
xếp theo khóa này.
Phương pháp chọn (Selection sort)
1. Ý tưởng
Chọn phần tửnhỏnhất trong n phần tử đầu, đưa phần tử
này vềvịtrí đầu của dãy.
Tiếp tục quá trình với n-1 phần tửcòn lại và bắtđầu từvịtrí
thứ2, lặp lại quá trình trên cho dãy gồm n-1 phần tửcòn lại.
Thuật toán thực hiện n-1 lầnđể lần lượtđưa phần tửnhỏ
nhất trong dãy hiện hành vềvịtrí dẫnđầu