48
Chương 3:
KỸ THUẬT SẮP XẾP
49
NỘI DUNG CHƯƠNG 3
1. Khái quát về sắp xếp
2. Các phương pháp sắp xếp (Sắp xếp trên dãy)
•Sắp xếp bằng phương pháp đổi chỗ (Exchange)
•Sắp xếp bằng phương pháp chọn (Selection)
•Sắp xếp bằng phương pháp chèn (Insertion)
•Sắp xếp bằng phương pháp trộn (Merge)
3. Các phương pháp sắp xếp (Sắp xếp trên tập tin)
•Sắp xếp tập tin bằng phương pháp trộn
•Sắp xếp tập tin theo chỉ mục
50
1. Khái quát về sắp xếp
Sắp xếp là thao tác cần thiết thường được thực hiện trong quá trình lưu trữ
và quản lý dữ liệu.
Thứ tự dữ liệu có thể tăng hay giảm, tăng hay giảm thuật toán sắp xếp là
tương tự.
Hai nhóm giải thuật sắp xếp
•Các giải thuật sắp xếp thứ tự nội (sx thứ tự trên mảng)
•Các giải thuật sắp xếp thứ tự ngoại (sx thứ tự trên tập tin)
Xem như mỗi phần tử dữ liệu được xem xét có một thành phần khóa (Key)
để nhận diện có kiểu dữ liệu T, các thành phần còn lại là thông tin (Info),
như vậy mỗi phần tử có cấu trúc như sau:
typedef struct DataElement
{
T Key;
InfoData Info;
} DataType;
Để đơn giản, quan tâm thành phần dữ liệu chỉ là khóa nhận diện
51
2. Sắp xếp trên dãy/mảng
2.1. Sắp xếp bằng phương pháp đổi chỗ (Exchange)
a. Thuật toán sắp xếp nổi bọt (Bubble Sort)
b. Thuật toán sắp xếp dựa trên phân hoạch (Partitioning
Sort) (thuật toán sx nhanh Quick Sort)
2.2. Sắp xếp bằng phương pháp chọn (Selection Sort)
Chọn trực tiếp (Straight Selection Sort)
2.3. Sắp xếp bằng phương pháp chèn (Insertion Sort)
Chèn trực tiếp (Straight Insertion Sort)
2.4. Sắp xếp bằng phương pháp trộn (Merge Sort)
a. Trộn trực tiếp (Straight Merge Sort)
b. Trộn tự nhiên (Natural Merge Sort)
52
2. Sắp xếp trên dãy/mảng
2.1. a. Thuật toán sắp xếp nổi bọt (Bubble Sort)
Ý tưởng:
•Đi từ cuối mảng đến đầu mảng, nếu phần tử ở dưới <
phần tử đứng trên nó thì sẽ được “đưa lên trên”.
•Sau mỗi lần đi duyệt dãy, 1 phần tử sẽ được đưa lên
đúng chỗ của nó. Đối với mảng M có N phần tử thì sau
N-1 lần đi duyệt dãy dãy M có thứ tự tăng.