Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4

KHOA CÔNG NGHỆ THÔNG TIN

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (Data Structures And Algorithms)

BÀI 4: CÁC GIẢI THUẬT SẮP XẾP NÂNG CAO

QUICK SORT

01.

MERGE SORT

02.

HEAP SORT

NỘI DUNG

03.

感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com

01. QUICK SORT •Thuật toán sắp xếp Quick Sort (sắp xếp nhanh) phức tạp hơn một chút so với các thuật toán sắp xếp khác. •Cho một danh sách các phần tử, thuật toán quick sort là thuật toán chia để trị, đệ quy bao gồm 3 phần chính: 1. Chọn một giá trị làm mốc (pivot value) 2. Phân vùng danh sách làm hai: danh sách trái (nhỏ hơn giá trị mốc), và danh sách phải (lớn hơn hoặc bằng giá trị mốc)

3. Đệ quy cho danh sách trái, đệ quy cho danh sách phải

3 KHOA CÔNG NGHỆ THÔNG TIN

01. QUICK SORT 1. Lấy một giá trị làm mốc: Lấy giá trị lớn nhất trong hai giá trị bên trái (3)

3 1 4 1 5 9 2 6 5 3

2. Phân vùng danh sách thành hai danh sách: một danh sách chứa các phần tử có giá trị < mốc, một danh sách chứa các phần tử có giá trị ≥ mốc

2 1 1

Danh sách 1 < mốc =

Danh sách 2 ≥ mốc =

4 5 9 3 6 5 3

Danh sách 2

Danh sách 1 2 1 1

3. Đệ quy

4 5 9 3 6 5 3

4 3 3

9 6 5 5

1 1 xong

2 xong

5 6 5

4 xong

3 3 xong

9 xong

Đây là danh sách được sắp cuối cùng…

6 xong

5 5 xong

4 KHOA CÔNG NGHỆ THÔNG TIN

01. QUICK SORT

3 1 4 1 5 9 2 6 5 3

r l 3 1 4 1 5 9 2 6 5 3

pval

3

l là biên trái, r là biên phải

r

l 3 1 4 1 5 9 2 6 5 3

l 2 1 4 1 5 9 3 6 5 3

l từ biên trái tìm ptử ≥ pval, r từ biên phải tìm ptử < pval

Nếu l != r Hoán vị ptử l với r

l r

2 1 4 1 5 9 3 6 5 3

l r

Khi l < r, tìm tiếp l và r

2 1 1 4 5 9 3 6 5 3

Nếu l != r Hoán vị ptử l với r

l,r

2 1 1 4 5 9 3 6 5 3

2 1 1

4 5 9 3 6 5 3

Khi l < r, tìm tiếp l và r. Dừng khi l ≥ r

Tách làm 2 danh sách dựa vào chỉ mục l

5 KHOA CÔNG NGHỆ THÔNG TIN

01. QUICK SORT

public int[] sort( int[] list ) { Giao diện return (qsort( list, 0, list.Length - 1 ));

} // Sort

private int[] qsort( int[] list, int left, int right ) {

int pval, l = left, r = right, temp;

if ( l == r )

return list;

if ( list[l] >= list[l+1] )

pval = list[l];

else

Lấy giá trị lớn nhất trong hai số bên trái trong danh sách pval = list[l+1];

6 KHOA CÔNG NGHỆ THÔNG TIN

01. QUICK SORT

Ở đây ta phân vùng danh sách thành hai danh sách. Đây là hai danh sách ảo là danh sách được xác định bởi các chỉ số, không phải hai mảng riêng biệt…

while ( l < r ) {

while (( list[l] < pval ) && ( l < r ))

l ++;

while (( list[r] >= pval ) && ( l < r ))

r --; Chụm vào từ bên phải và bên trái cho đến khi tìm thấy các giá trị để hoán vị hoặc ta chạy hết các phần tử trong danh sách.

7 KHOA CÔNG NGHỆ THÔNG TIN

01. QUICK SORT

if ( l != r ) {

temp = list[l]; list[l] = list[r]; list[r] = temp; Nếu chỉ mục trái khác chỉ mục phải là ta đã tim được các giá trị để hoán vị, và ở đây ta thực hiện hoán vị…

} // if } // while

qsort( list, left, l-1 ); qsort( list, l, right );

Nếu xảy ra bất kỳ hoán vị nào thì ta đệ quy; ngược lại, ta kết thúc… return list;

} // qsort

8 KHOA CÔNG NGHỆ THÔNG TIN

01. QUICK SORT

Hiệu năng của Quick Sort bị tác động bởi phần tử được chọn làm điểm mốc.

Hiệu xuất của quick sort trong trường hợp xấu nhất, O(n2).

Trường hợp tổng quát, quick sort có sự thực thi O(n log n) thời gian biểu thị ở bên phải…

Quick Sort được coi là sắp xếp nhanh nhất

Ưu điểm: cực nhanh

Nhược điểm: rất phức tạp đệ quy ồ ạt

9 KHOA CÔNG NGHỆ THÔNG TIN

02. MERGE SORT •Merge Sort (Sắp Xếp Trộn) cũng là thuật toán đệ quy, chia để trị •Các bước của thuật toán là:

̶ Đệ quy phân vùng danh sách đầu vào thành hai danh sách, L1 và L2 khoảng n/2 phần tử mỗi danh sách cho đến khi ta có tập các danh sách với 1 hoặc 2 phần tử trong mỗi danh sách.

̶ Đến đây, mỗi L1 và L2 được trộn lại thành danh sách duy nhất S, các phần tử của L1 và L2 được đưa vào danh sách S theo thứ tự.

10 KHOA CÔNG NGHỆ THÔNG TIN

02. MERGE SORT

Merge Sort tương đối đơn giản như sau:

void MergeSort(int[] arr, int left, int right) {

if(left < right) { Kết thúc khi danh sách chỉ có 1 phần tử int mid = (left + right) / 2;

MergeSort(arr, left, mid); MergeSort(arr, mid + 1, right); Xác định phần tử giữa để chia danh sách

Merge(arr, left, mid, right);

} Chia thành hai tập L1, L2 và đệ quy

}

Trộn L1 và L2 với nhau cho ra danh sách được sắp xếp

11 KHOA CÔNG NGHỆ THÔNG TIN

02. MERGE SORT

void Merge(int[] arr, int left, int mid, int right) {

int[] leftarray = new int[mid - left + 1]; int[] rightarray = new int[right - mid];

Array.Copy(arr, left, leftarray, 0, mid - left + 1); Array.Copy(arr, mid + 1, rightarray, 0, right - mid);

Tạo hai mảng con leftarray (L1), rightarray (L2)

12 KHOA CÔNG NGHỆ THÔNG TIN

02. MERGE SORT int i = 0; int j = 0; for(int k = left; k < right + 1; k++){

if(i == leftarray.Length){

arr[k] = rightarray[j]; j++;

} else if(j == rightarray.Length){ arr[k] = leftarray[i]; i++;

} else if(leftarray[i] <= rightarray[j]){ Trộn các phần tử trong mảng leftarray, mảng rightarray vào mảng arr theo thứ tự giá trị phần tử

arr[k] = leftarray[i]; i++;

} else{

arr[k] = rightarray[j]; j++;

}

13 KHOA CÔNG NGHỆ THÔNG TIN

02. MERGE SORT

3 1 4 1 5 9 2 6 5 3

3 1 4 1 5

9 2 6 5 3

5 3

3 1 4

1 5

9 2 6

3 1

9 2

2 9

1 3

2 6 9

1 3 4

1 5

3 5

2 3 5 6 9

1 1 3 4 5

1 1 2 3 3 4 5 5 6 9

14 KHOA CÔNG NGHỆ THÔNG TIN

02. MERGE SORT •Ta có thể thấy rằng thời gian chạy của merge sort cho danh sách có độ dài n là T(n) •Vì ta cắt đôi danh sách và sau đó đệ quy, ta có thể kết luận: 2T(n/2)+n •Lưu ý là ta cộng them n bước để trộn kết quả hai danh sách •Hiệu năng trung bình của Merger Sort là O(n log n) •Merge Sort yêu cầu không gian nhớ O(n) •Merge Sort có thể là một lựa chọn tối ưu vì nó thực thi ngang bằng với Quick Sort nhưng sử dụng ít bộ nhớ hơn

15 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT •Heap Sort (Sắp xếp vun đống) là thuật toán sắp xếp dựa trên cấu trúc dữ liệu Binary Heap (Đống nhị phân). Tìm phần tử lớn nhất và đặt nó ơ cuối danh sách; lặp lại cho danh sách gồm các phần tử còn lại. •Binary Heap là gì?

▪ Binary Heap là một Complete Binary Tree (cây nhị phân hoàn chỉnh) với nút cha có giá trị lớn hơn giá trị hai nút con. ▪ Cây nhị phân hoàn chỉnh là cây nhị phân trong đó mọi cấp,

ngoại trừ cấp cuối cùng, được lấp đầy hoàn toàn.

• Mảng biểu diễn cho đống nhị phân. Nếu nút cha lưu ở chỉ mục i thì

nút con bên trái là 2i+1, và nút con bên phải là 2i+2.

16 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

12 11 13 5 6 7

12 13

11 11 13 12

7 6 5 7 6 5

Đống nhị phân (Binary Heap)

Cây nhị phân hoàn chỉnh (Complete Binary Tree)

17 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT •Thuật toán Heap Sort cho sắp xếp tăng dần:

1. Tạo Binary Heap (đống nhị phân) từ danh sách 2. Lúc này, phần tử lớn nhất được lưu ở nút gốc của đống. Hoán vị nó với phần tử cuối cùng của đống. Giảm kích thước đống đi 1 đơn vị. Cuối cùng, chất đống gốc của cây

3. Lặp lại các bước trên khi kích thước của đống lớn hơn 1

18 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

Ví dụ 1:

7 11 12 5 6 13 13 11 12 5 6 7 12 11 13 5 6 7

7 13 12

11 11 12 11 12 13

13 6 5 7 6 5 7 6 5

Đống nhị phân (Binary Heap) Cây nhị phân hoàn chỉnh (Complete Binary Tree)

19 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

7 11 12 5 6 13 6 11 7 5 12 7 11 12 5 6 12 11 7 5 6

7 6 7 12

11 11 11 11 12 7 12 7

5 13 6 5 12 6 5 6 5

Đống nhị phân (Binary Heap)

20 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

5 6 7 11 6 11 7 5 11 6 7 5 6 11 7 5 12

5 6 11 6

6 11 6 11 7 7 7 7

11 5 5 5 12

Đống nhị phân (Binary Heap)

21 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

5 6 7 7 6 5 5 6 7 11 5 6 7

5 7 5 5

6 6 6 7 6 5 7 7

Đống nhị phân (Binary Heap) 11

22 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

5 6 5 5 6 5 6 5 6 7

5 6 5 5 5

5 6 6 6 7

Đống nhị phân (Binary Heap)

12 11 13 5 6 7 5 6 7 11 12 13

23 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

Ví dụ 2:

4 10 3 5 1 10 4 3 5 1 10 5 3 4 1 1 5 3 4 10

4 10 10 1

10 4 5 5 3 3 3 3

5 5 4 4 1 1 1 10

Đống nhị phân (Binary Heap)

24 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

1 5 3 4 10 1 5 3 4 5 1 3 4 5 4 3 1 1 4 3 5

1 1 5 5 1

5 5 1 4 3 4 3 3 3 3

4 4 4 1 5 10

Đống nhị phân (Binary Heap)

25 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

1 4 3 5 1 4 3 4 1 3 3 1 4

1 1 4 3

4 4 1 1 3 3 3 4

5 Đống nhị phân (Binary Heap)

26 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

3 1 4 3 1 3 1 1 3 1

3 3 3 1 1

1 1 1 3 4

Đống nhị phân (Binary Heap)

1 3 4 5 10 4 10 3 5 1

27 KHOA CÔNG NGHỆ THÔNG TIN

public void sort(int[] arr) { int n = arr.Length;

// Tạo đống (sắp xếp lại mảng) for(int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);

// Từng bước trích xuất một phần tử ra khởi đống for(int i = n - 1; i > 0; i--){ // Di chuyển nút gốc hiện tại đến cuối int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;

// Gọi max heapify trên đống đã giảm heapify(arr, i, 0); } }

28 KHOA CÔNG NGHỆ THÔNG TIN

void heapify(int[] arr, int n, int i){ int largest = i; // Khởi gán largest là nút gốc int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2

// Nếu nút con trái lớn hơn nút gốc if(l < n && arr[l] > arr[largest]) largest = l; // Nếu nút con phải lớn hơn nút largest lúc này if(r < n && arr[r] > arr[largest]) largest = r;

// Nếu largest không phải là nút gốc if(largest != i){ int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap;

// Đệ quy heapify tác động lên cây con heapify(arr, n, largest); } }

29 KHOA CÔNG NGHỆ THÔNG TIN

03. HEAP SORT

•Độ phức tạp của Heap Sort là: O (n log n) •Thuật toán Heap Sort đã bị giới hạn sử dụng vì thực tế Quick Sort và Merge Sort thì tốt hơn. Tuy nhiên, cấu trúc dữ liệu Heap (đống ) được sử dụng nhiều.