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
After pass 1
78
45
23
32
56
8
After pass 2
23
45
78
32
56
8
After pass 3
23
32
78
45
56
8
After pass 4
23
32
45
78
56
8
After pass 5
23
32
45
56
78
8
Chọn trực tiếp
Chọn trực tiếp void SelectionSort(int a[], int n){
for(int i=0;i<=n-2;i++){
int iMin =i;
for(int j=i+1;j if(a[j] }
int t= a[i]; a[i] = a[iMin]; a[iMin]=t; } } 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 = 𝑛 − 1 + 𝑛 − 2 + ⋯ + 1 = 𝑆𝑆 = 𝑖=0 𝑛−1 𝑛
2 Độ phức tạp của thuật toán: 𝑂 𝑛2 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. 23 78 45 8 32 56 Original List After pass 1 23 78 45 8 32 56 After pass 2 23 45 78 8 32 56 After pass 3 8 23 45 78 32 56 After pass 4 8 23 32 45 78 56 After pass 5 8 23 32 45 56 78 void InsertionSort(int a[], int n){ for(int i=1;i int x = a[i];
int j= i-1;
while(a[j]>x){ a[j+1]=a[j];j--; if(j==-1)break; }
a[j+1]=x; } } 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 2𝑖 = 2 1 + 2 + ⋯ + 𝑛 − 1 = 𝑛(𝑛 − 1) ≈ 𝑂(𝑛2) 𝑆𝑆 = 𝑖=1
Trung bình
𝑆𝑆 ≈ 𝑂(𝑛2) 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] sorted 6 4 7 2 3 sorted Bước 1 2 3 7 4 6 sorted 3 6 7 4 2 Bước 2 sorted 4 6 7 2 3 Bước 3 Bước 4 void BubbleSort(int a[],int n){ for(int i=n-1;i>=1;i--){
for(int j=1; j<=i;j++) if(a[j-1]>a[j]){ int temp =a[j-1];
a[j-1]=a[j];
a[j] = temp; } } } 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: ≈ 𝑂(𝑛2) 𝑆𝑆 = 𝑖=1 𝑛−1 𝑛
2 𝑛−1 𝑖 = 1 + 2 + ⋯ + 𝑛 − 1 =
Độ phức tạp của thuật toán: 𝑂(𝑛2) 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;i if(a[i]>a[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] a[i-1]=t; exchange=true; k=i;} jMax=k; }while(exchange); } Ý 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 Đánh giá sơ lược giải thuật chia để trị Giả sử 2 danh sách có số phần tử là n’ = n/2
Dùng insertion sort riêng cho từng mảnh
Trộn 2 danh sách tốn (n’ + n’) = n lần so sánh
Số lần so sánh tổng cộng: 2*((n/2)2/2 + O(n/2)) + n = n2/4 + O(n) So sánh với insertion sort là n2/2 + O(n)
Có vẻ nhanh hơn Finish Start 26 33 35 29 19 12 22 12 19 22 26 29 33 35 Trộn 12 19 22 26 33 35 29 26 29 33 35 19 12 22 Trộn Trộn 26 33 26 33 35 29 29 35 19 12 12 19 22 Trộn Trộn Trộn 26 33 35 29 19 12 void Merge(int a[], int first, int last){ int mid = (first +last)/2;
int first1= first, last1=mid;
int first2=mid+1, last2=last;
int temp[MAX_SIZE];
int i=first1, j=first2, k=0;
while ((i<=last1)&&(j<=last2))
{ if(a[i]<=a[j])temp[k++]=a[i++];
else temp[k++] = a[j++]; }
if(i>last1) //mảng bên trái hết phần tử
while(j<=last2)temp[k++]=a[j++];
if(j>last2) //mảng bên phải hết phần tử
while(i<=last1)temp[k++]=a[i++]; for(i=first;i<=last;i++)a[i]=temp[i-first]; //copy mảng tạm vào a[first..last] } void MergeSort(int a[], int first, int last){
if(first phần tử int mid = (first +last)/2;
MergeSort(a,first,mid);
MergeSort(a, mid+1, last);
Merge(a,first, last); } } Merge Sort – Ví dụ divide 6 3 9 1 5 4 7 2 divide divide 7 2 6 3 9 1 5 4 7 2 6 3 9 1 divide divide divide divide 5 4 merge merge merge merge 6 3 9 1 5 4 7 2 4 5 merge merge 2 7 1 9 3 6 merge 1 2 3 4 5 7 8 9 1 3 6 9 2 4 5 7 Phân tích thuật toán Merge 0 k-1
...... 0 k-1
...... Trộn hai mảng kích cỡ k 0 2k-1
...... Tốt nhất: Tất cả phần tử trong mảng trái nhỏ hơn phần tử trong mảng phải.
Số phép so sánh: k + 1 Xấu nhất: i = k-1 và j = k-1
Số phép so sánh: 2k Các cấp gọi đệ qui của mảng có 8 phần tử 2m 2m-1 2m-1 level 0 : 1 merge (size 2m-1) level 1 : 2 merges (size 2m-2) 2m-2 2m-2 2m-2 2m-2 .
.
. .
.
. level 2 : 4 merges (size 2m-3) 20 20 level m-1 : 2m-1 merges (size 20) . . . . . . . . . . . . . . . . . level m Xấu nhất
Số phép so sánh: = (2*20 )*2m-1 + (2*21)*2m-2 + ... + (2*2m-1)*20
= 2m + 2m + ... + 2m ( m hạng tử ) = m*2m O (n * log2n ) Merge Sort là thuật toán hiệu quả xét trên phương diện độ phức tạp tính toán và thời gian.
Độ phức tạp trong cả trường hợp tốt nhất và xấu nhất: O (n * log2n ) Để trộn hai mảng con của một mảng cho trước, đòi
hỏi một mảng có kích cỡ bằng kích cỡ mảng ban
đầu . Quick Sort Sort (26, 33, 35, 29, 19, 12, 22) Phân thành (19, 12, 22) và (33,35,29) với pivot=26 Sort (19, 12, 22) Phân thành (12) và (22) với pivot=19 Sort (12)
Sort (22)
Combine into (12, 19, 22) Sort (33, 35, 29) Phân thành (29) và (35) với pivot=33 Sort (29)
Sort (35)
Combine into (29, 33, 35) Combine into (12, 19, 22, 26, 29, 33, 35) Algorithm Quick Sort
Input: mảng cần sắp
Output: mảng đã được sắp xếp 1. if (có ít nhất 2 phần tử) //Phân hoạch mảngthành 3 phần:
//- Phần nhỏ hơn phần tử giữa
//- Phần tử giữa
//- Phần lớn hơn phần tử giữa
1.1. Phân hoạch mảng thành 3 phần
1.2. Call QuickSort cho phần bên trái
1.3. Call QickSort cho phần bên phải
//Chỉ cần ghép lại là thành danh sách có thứ tự End void QuickSort(int a[], int low, int high){ if(low int pivot_pos = Partition(a, low, high);
QuickSort(a,low,pivot_pos);
QuickSort(a, pivot_pos+1, high); } } int Partition(int a[], int low, int high){ int mid = (low + high)/2;
Swap(a[low], a[mid]);
int pivot = a[low];
int last_small = low;
for(int i= low+1; i<=high; i++)
if(a[i] last_small ++; Swap(a[last_small],a[i]); }
Swap(a[low],a[last_small]);
return last_small; } QuickSort(0,6) 0 1 2 3 4 5 6 pivot
26 pivot_position = Partition(0,6) = 3 19 35 33 26 29 12 22 low=0 high=6 last_small mid=(low+high)/2=3 pivot_position QuickSort(0,2) index QuickSort(4,6) QuickSort(0,2) 0 1 2 3 4 5 6 pivot
19 pivot_position = Partition(0,2) = 1 22 19 12 26 29 33 35 low=0 high=2 mid=(low+high)/2=1 last_small index (Không làm gì cả) QuickSort(0,0)
QuickSort(2,2) pivot_position QuickSort(4,6) 0 1 2 3 4 5 6 pivot
33 pivot_position = Partition(4,6) = 5 12 19 22 26 29 33 35 low=4 high=6 mid=(low+high)/2=5 last_small index (Không làm gì cả) QuickSort(4,4)
QuickSort(6,6) pivot_position Trường hợp xấu nhất: Một bên rỗng và một bên là n-1 phần tử => n(n-1)/2 Chọn phần tử pivot: Đầu (hay cuối): trường hợp xấu xảy ra khi danh sách đang có thứ tự (hoặc thứ tự ngược) Ở trung tâm, hoặc ngẫu nhiên: trường hợp xấu khó xảy ra Trường hợp trung bình: C(n) = 2n ln n + O(n) ≈ 1.39 n lg n + O(n) ≈O(nlogn) Mảng có n phần tử (từ 0 đến n-1)
ak ≥ a2k+1 và ak ≥ a2k+2 (ak lớn nhất trong 3 phần tử) Đặc tính: a0 là phần tử lớn nhất
Heap chưa chắc có thứ tự
Nửa sau của mảng bất kỳ thỏa định nghĩa heap Heap sort: Lấy a0 ra, tái tạo lại heap => Phần tử lớn nhất
Lấy a0 mới ra, tái tạo lại heap => Phần tử lớn kề
… void HeapSort(int a[], int n){ //xây dựng heap ban đâu
BuildHeap(a,n); //mảng đã là một heap
for(int i=n-1; i>=1; i--){ int current = a[i];
a[i]= a[0]; //chuyển phần tử lớn nhất về cuối
//a[1..i-1] đang là heap, thêm current vào để
vẫn là heap
InsertHeap(current,a,0,i-1); } } Dạng cây nhị phân:
Node gốc là a0
2 node con của phần tử
ak là 2 phần tử a2k+1 và
a2k+2 Ở mức cuối cùng, các node lấp đầy từ bên trái
sang bên phải (cây nhị
phân gần đầy đủ) 0 1 2 3 4 5 6 7 8 y r p d f b k current a c 0
y 1
r 2
p 3
d 4
f 5
b 6
k 7
a 8
c r f p d c b k current a y 0
r 1
f 2
p 3
d 4
c 5
b 6
k 7
a 8
y p f k d c b a current r y 0
p 1
f 2
k 3
d 4
c 5
b 6
a 7
r 8
y k f b d c a p current r y 0
k 1
f 2
b 3
d 4
c 5
a 6
p 7
r 8
y f d b a c k p current r y 0
f 1
d 2
b 3
a 4
c 5
k 6
p 7
r 8
y d c b a f k p current r y 0
d 1
c 2
b 3
a 4
f 5
k 6
p 7
r 8
y c a b d f k p current r y 0
c 1
a 2
b 3
d 4
f 5
k 6
p 7
r 8
y b a c d f k p current r y 0
b 1
a 2
c 3
d 4
f 5
k 6
p 7
r 8
y Giải thuật tái tạo lại Heap Algorithm InsertHeap cần thêm vào Output: mảng là heap trong khoảng từ low đến high 1. Bắt đầu kiểm tra tại vị trí low
2. while (chưa kiểm tra xong đến high) 2.1. Tìm lớn nhất trong bộ ba phần tử current, a[2k+1], a[2k+2]
2.2. if (phần tử đó là current) 2.2.1. Ngừng vòng lặp 2.3. else 2.3.1. Dời phần tử lớn nhất lên vị trí hiện tại
2.3.2. Kiểm tra bắt đầu từ vị trí của phần tử lớn nhất này 3. Đưa current vào vị trí đang kiểm tra End Output: thêm current vào sao cho mảng a[low…high] vẫn là một heap void InsertHeap(int current,int a[], int low, int high)
{ int large = 2*low +1;
while(large <=high){//chưa xét hết phần tử if(large if(a[large +1]>a[large])large++; if(current>=a[large])break;
a[low]=a[large]; //di chuyển phần tử max
low = large;
large = 2*low +1; }
a[low]=current; //chuyển current vào vị trí đang xét } void BuildHeap(int a[],int n){ //nửa sau từ n/2 --> n-1 đã là một heap
for(int i=n/2-1; i>=0; i--){ int current = a[i];
InsertHeap(current,a,i,n-1); } } 0
p 1
c 2
y 3
d 4
f 5
b 6
k 7
a 8
r Bước 1 0
p 1
c 2
y 3
r 4
f 5
b 6
k 7
a 8
d 0
p 1
c 2
y 3
r 4
f 5
b 6
k 7
a 8
d Bước 2 Bước 3 0
p 1
r 2
y 3
d 4
f 5
b 6
k 7
a 8
c 0
p 1
r 2
y 3
c 4
f 5
b 6
k 7
a 8
d Bước 3’ Bước 4 0
y 1
r 2
p 3
d 4
f 5
b 6
k 7
a 8
c Trường hợp xấu nhất và trung bình: C = 2n lg n + O(n)
M = n lg n + O(n) So với Quick Sort Trung bình: chậm hơn quick sort
Xấu nhất: O(n lg n) < n(n-1)/2 Radix sort khác với các phương pháp sắp xếp khác. Radix sort Xem các phần tử như các chuỗi
Nhóm các phần tử có cùng kí tự tận cùng phải
Nhập các nhóm lại với nhau
Lập lại bước trên cho tất cả các vị trí từ vị trí tận cùng
phải (rightmost) cho đến vị trí tận cùng trái (leftmost) mom, dad, god, fat, bad, cat, mad, pat, bar, him original list
(dad,god,bad,mad) (mom,him) (bar) (fat,cat,pat) group strings by rightmost letter combine groups combine groups dad,god,bad,mad,mom,him,bar,fat,cat,pat
(dad,bad,mad,bar,fat,cat,pat) (him) (god,mom) group strings by middle letter
dad,bad,mad,bar,fat,cat,pat,him,god,mom
(bad,bar) (cat) (dad) (fat) (god) (him) (mad,mom) (pat) group strings by first letter bad,bar,cat,dad,fat,god,him,mad,mom,par combine groups (SORTED) d:integer) // sort n d-digit integers in the array theArray k = chữ số thứ j của theArray[i]
Đặt theArrar[i] vào nhóm thứ k
Tăng counter thứ k thêm 1 }
Thay thế các phần tử trong theArray bởi các phần tử
trong nhóm 1, nhóm 2,… theo thứ tự } Đòi hỏi 2*n*d phép gán để sắp n chuỗi có chiều dài là d Độ phức tạp O(n) Trình bày cách thực hiện sắp xếp mảng sau theo các thuật toán (ghi kết quả sau từng bước)
Selection Sort
Insertion Sort
Buble Sort
Merge Sort
Quick Sort A={10, 3, 7, 6, 2, 5, 4, 16, 20, 1 }Đánh giá chọn trực tiếp
Chèn trực tiếp (Insertion Sort)
Sorted
Unsorted
Chèn trực tiếp
Chèn trực tiếp
Đánh giá chèn trực tiếp
Nổi bọt (Bubble Sort)
Nổi bọt
Nổi bọt
Đánh giá Bubble Sort
Cải tiến Bubble Sort
Chia để trị
Merge sort
Trộn hai mảng con tăng
Merge Sort
Phân tích thuật toán Merge
Trường hợp xấu nhất
Phân tích Merge Sort
Phân tích Merge Sort
Đánh giá Merge Sort
Thay m = log n
Số phép so sánh:
= n * log2n
Đánh giá Merge Sort
Quick Sort
Quick Sort
Phân hoạch cho Quick Sort
Phân hoạch cho Quick Sort
Partition Quick Sort
Ví dụ Quick Sort
Ví dụ Quick Sort
Ví dụ Quick Sort
Các trường hợp của Quick sort
Đánh giá Quick Sort
Heap và Heap Sort
Heap (định nghĩa lại):
Heap Sort
Biểu diễn Heap
Ví dụ Heap Sort
Ví dụ Heap Sort
Ví dụ Heap Sort
Ví dụ Heap Sort
Ví dụ Heap Sort
Ví dụ Heap Sort
Ví dụ Heap Sort
Ví dụ Heap Sort
Input: mảng là heap trong khoảng từ low+1 đến high, current là giá trị
Giải thuật tái tạo Heap
Input: InsertHeap(current, a[], low, high)
Mảng a[low+1…high] đã là một heap
Xây dựng Heap ban đầu
Ví dụ xây dựng Heap ban đầu
Đánh giá Heap Sort
Radix Sort
Radix Sort – Ví dụ
Radix Sort – Ví dụ
Radix Sort - Algorithm
void RadixSort(inout theArray:ItemArray, in n:integer, in
for (j=d; j>=1; j--) {
Khởi tạo 10 nhóm bằng rỗng
Khởi tạo các counter của các nhóm bằng 0
for (i=0; i
Đánh giá Radix Sort
So sánh các giải thuật
Luyện tập
