TS. Lê Minh Trung
Th.S Lương Trần Ngọc Khiết
Khoa CNTT, Đại học Sư phạm TP. HCM
Nội dung
Chọn trực tiếp (Selection Sort)
Chèn trực tiếp (Insertion Sort)
Nổi bọt (Bubble Sort)
Merge Sort
Quick Sort
Heap Sort
Radix Sort
Khái niệm
Sắp thứ tự:
Đầu vào: một mảng
Đầu ra: mảng có thứ tự tăng (hoặc giảm) trên khóa
Phân loại:
Sắp thứ tự ngoại (external sort): tập tin
Sắp thứ tự nội (internal sort): bộ nhớ
Giả thiết:
Sắp thứ tự nội
Sắp tăng dần
Chọn trực tiếp
Input: int a[n]
Output: mảng đã được sắp xếp
Ý tưởng:
Với mỗi i=0, 1, 2,…, n-2
Tìm phần tử nhỏ nhất của mảng con a[i..n-1] và hoán vị phần
tử này với a[i].
23 78 45 8 32 56
878 45 23 32 56
823 45 78 32 56
823 32 78 45 56
823 32 45 78 56
823 32 45 56 78
Original List
After pass 1
After pass 2
After pass 3
After pass 4
After pass 5
Sorted Unsorted