Xem mẫu
- 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].
- Sorted Unsorted
23 78 45 8 32 56 Original List
8 78 45 23 32 56 After pass 1
8 23 45 78 32 56 After pass 2
After pass 3
8 23 32 78 45 56
8 23 32 45 78 56 After pass 4
After pass 5
8 23 32 45 56 78
- Chọn trực tiếp
- Chọn trực tiếp
void SelectionSort(int a[], int n){
for(int i=0;i
- Đánh giá chọn trực tiếp
Vòng lặp for ngoài có n-1 lần lặp i=0,1,…,n-2
Số phép so sánh của lần lặp thứ i: n-i-1
Số phép so sánh:
𝑛−2 𝑛−1 𝑛
𝑆𝑆 = 𝑖=0 𝑛 − 𝑖 − 1 =𝑛 − 1 + 𝑛 − 2 + ⋯+ 1 =
2
Độ phức tạp của thuật toán: 𝑂 𝑛2
- Chèn trực tiếp (Insertion Sort)
Input: int a[n]
Output: mảng đã được sắp xếp
Ý tưởng:
Với mỗi i=1,2,…,n-1
Mảng con a[0..i-1] đã được sắp thứ tự tăng, chèn a[i] vào vị
trí thích hợp để mảng con a[0..i] sắp thứ tự tăng.
- Sorted Unsorted
23 78 45 8 32 56 Original List
23 78 45 8 32 56 After pass 1
23 45 78 8 32 56 After pass 2
After pass 3
8 23 45 78 32 56
8 23 32 45 78 56 After pass 4
After pass 5
8 23 32 45 56 78
- Chèn trực tiếp
- Chèn trực tiếp
void InsertionSort(int a[], int n){
for(int i=1;ix){
a[j+1]=a[j];j--; if(j==-1)break;
}
a[j+1]=x;
}
}
- Đánh giá chèn trực tiếp
Vòng lặp for ngoài có n-1 lần lặp i=1,2,…,n-1
Tốt nhất
𝑆𝑆 = 𝑛−1
𝑖=1 1 = 𝑛 − 1 ≈ 𝑂(𝑛)
Xấu nhất
𝑛−1
𝑆𝑆 = 𝑖=1 2𝑖 = 2 1 + 2 + ⋯ + 𝑛 − 1 = 𝑛(𝑛 − 1) ≈ 𝑂(𝑛2 )
Trung bình
𝑆𝑆 ≈ 𝑂(𝑛2 )
- Nổi bọt (Bubble Sort)
Input: int a[n]
Output: mảng đã được sắp xếp
Ý tưởng:
Với mỗi i=n-1, n-2,…, 1
Với mỗi j=0, 1,…, i
Nếu a[j]
- Nổi bọt
sorted
Bước 1 6 4 7 2 3
sorted
Bước 2 4 6 2 3 7
sorted
Bước 3 4 2 3 6 7
sorted
Bước 4 2 3 4 6 7
- Nổi bọt
void BubbleSort(int a[],int n){
for(int i=n-1;i>=1;i--){
for(int j=1; ja[j]){
int temp =a[j-1];
a[j-1]=a[j];
a[j] = temp;
}
}
}
- Đánh giá Bubble Sort
Vòng lặp for ngoài có n-1 lần lặp i=n-1, n-2, …, 2, 1
Vòng lặp for trong có i lần lặp j=1, 2, …, i
Mỗi lần lặp có 1 phép so sánh, số phép so sánh:
𝑛−1 𝑛−1 𝑛
𝑆𝑆 = 𝑖=1 𝑖 = 1 + 2 + ⋯+ 𝑛 − 1 = ≈ 𝑂(𝑛2 )
2
Độ phức tạp của thuật toán: 𝑂(𝑛2 )
- Cải tiến Bubble Sort
Cho phép nổi bọt theo hai chiều
Nổi bọt xuống, nổi bọt lên
Khi nổi bọt ghi nhận lại
Có sự nổi bọt thật sự hay không
exchange =false mảng đã được sắp thứ tụ
Vị trí nổi bọt cuối cùng
- Bubble Sort cải tiến
void BubbleSort(int a[],int n){
int iMax=n-1, jMax=0,t,k;
bool exchange = true;
do
{
exchange =false;
for(int i=jMax;ia[i+1]){t=a[i]; a[i]=a[i+1];
a[i+1]=t;exchange=true;k=i;}
iMax =k;
if(!exchange)break; //nếu không có hoán vị nào trước đó thì
thoát vì mảng đã được sắp thứ tự
exchange = false;
for(int i=iMax;i>jMax;i--) //nổi bọt lên
if(a[i]
- Chia để trị
Ý tưởng:
Chia danh sách ra làm 2 phần
Sắp thứ tự riêng cho từng phần
Trộn 2 danh sách riêng đó thành danh sách có thứ tự
Hai giải thuật:
Merge sort:
Chia đều thành 2 danh sách
Sắp thứ tự riêng
Trộn lại
Quick sort:
Chia thành 3 phần: nhỏ, giữa (pivot), lớn
Sắp thứ tự riêng
nguon tai.lieu . vn
