Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Tìm kiếm và sắp xếp nội

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

78
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 2: Tìm kiếm và sắp xếp nội" cung cấp cho người đọc các kiến thức: Các giải thuật tìm kiếm nội, các giải thuật sắp xếp nội. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Tìm kiếm và sắp xếp nội

CHƯƠNG 2 Nội Dung Nội Dung (Tt)  Các giải thuật tìm kiếm nội 4. Chèn trực tiếp – Insertion Sort 1. Tìm kiếm tuyến tính 5. Chèn nhị phân – Binary Insertion Sort 2. Tìm kiếm nhị phân 6. Shaker Sort TÌM KIẾM VÀ SẮP XẾP NỘI  Các giải thuật sắp xếp nội 7. Shell Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 8. Heap Sort 1. Đổi chỗ trực tiếp – Interchange Sort 9. Quick Sort 2. Chọn trực tiếp – Selection Sort 10. Merge Sort 3. Nổi bọt – Bubble Sort 11. Radix Sort 1 2 3 Bài Toán Tìm Kiếm Tìm Kiếm Tuyến Tính Thuật Toán Tìm Kiếm Tuyến Tính  Cho danh sách có n phần tử a0, a1, a2…, an-1.  Ý tưởng : So sánh X lần lượt với phần tử thứ 1,  Hàm trả về 1 nếu tìm thấy, ngược lại trả về 0: thứ 2,…của mảng a cho đến khi gặp được khóa  Để đơn giản trong việc trình bày giải thuật ta dùng int LinearSearch(int a[],int n, int x) cần tìm, hoặc tìm hết mảng mà không thấy. { mảng 1 chiều a để lưu danh sách các phần tử nói trên trong bộ nhớ chính.  Các bước tiến hành int i=0; • Bước 1: Khởi gán i=0; while((i
Minh Họa Thuật Toán Tìm Kiếm Tuyến Tính Minh Họa Thuật Toán Tìm Kiếm Tuyến Tính (tt) Ðánh Giá Thuật Toán Tìm Tuyến Tính Trường hợp Css X=10 i=7, không tìm thấy Tốt nhất 1 X=6 Tìm thấy 6 tại vị trí 4 i i 2 8 5 1 6 4 6 Xấu nhất N CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 2 8 5 1 6 4 6 0 1 2 3 4 5 6 Trung bình (N+1) / 2 0 1 2 3 4 5 6  Độ phức tạp O(N) 7 8 9 Cải Tiến Thuật Toán Tìm Tuyến Tính Thuật Toán Tìm Kiếm Nhị Phân Các Bước Thuật Toán Tìm Kiếm Nhị Phân  Nhận xét: Số phép so sánh của thuật toán trong trường  Được áp dụng trên mảng đã có thứ tự.  Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử hợp xấu nhất là 2*n. nằm trong aleft, aright, các bước của giải thuật như sau:  Ý tưởng: .  Để giảm thiểu số phép so sánh trong vòng lặp cho thuật  Giả xử ta xét mảng có thứ tự tăng, khi ấy ta có  Bước 1: left=0; right=N-1; toán, ta thêm phần tử “lính canh” vào cuối dãy.  Bước 2: ai-1
Cài Đặt Thuật Toán Tìm Nhị Phân Ðánh Giá Thuật Toán Tìm Tuyến Tính Minh Họa Thuật Toán Tìm Nhị Phân  Hàm trả về giá trị 1 nếu tìm thấy, ngược lại hàm trả về giá trị 0 Trường hợp Css int BinarySearch(int a[],int n,int x) Tìm thấy 2 tại vị trí 1 { int left, right, mid; left=0; right=n-1; Tốt nhất 1 X=2 do{ mid=(left+right)/2; Xấu nhất L M R log2N CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT if(a[mid]==x) return 1; 1 2 4 6 7 9 10 else if(a[mid]
Các Thuật Toán Sắp Xếp Các Thuật Toán Sắp Xếp Đổi Chỗ Trực Tiếp – Interchange Sort 1. Đổi chỗ trực tiếp – Interchange Sort 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort  Ý tưởng: Xuất phát từ đầu dãy, tìm tất các 3. Nổi bọt – Bubble Sort 4. Shaker Sort 4. Shaker Sort các nghịch thế chứa phần tử này, triệt tiêu 5. Chèn trực tiếp – Insertion Sort chúng bằng cách đổi chỗ 2 phần tử trong cặp 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 6. Chèn nhị phân – Binary Insertion Sort nghịch thế. Lặp lại xử lý trên với phần tử kế 7. Shell Sort 7. Shell Sort 8. Heap Sort trong dãy. 8. Heap Sort 9. Quick Sort 9. Quick Sort 10. Merge Sort 10. Merge Sort 11. Radix Sort 11. Radix Sort 19 20 21 Các Bước Tiến Hành Đổi Chỗ Trực Tiếp – Interchange Sort Đổi Chỗ Trực Tiếp – Interchange Sort  Bước 1: i = 0; // bắt đầu từ đầu dãy  Cho dãy số a:  Bước 2: j = i+1; //tìm các nghịch thế với a[i] 12 2 8 5 1 6 4 15  Bước 3: i=1 j=2 Trong khi j < N thực hiện Nếu a[j]
Đổi Chỗ Trực Tiếp – Interchange Sort Đổi Chỗ Trực Tiếp – Interchange Sort Đổi Chỗ Trực Tiếp – Interchange Sort i=3 j=4 i=4 j=5 i=2 j=3 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i=3 j=5 i=2 j=4 i=4 j=6 i=5 j=6 i=2 j=6 25 i=3 j=6 26 27 Đổi Chỗ Trực Tiếp – Interchange Sort Cài Đặt Đổi Chỗ Trực Tiếp Minh Họa Thuật Toán void InterchangeSort(int a[], int N ) { int i, j; for (i = 0 ; i
Minh Họa Thuật Toán Minh Họa Thuật Toán Minh Họa Thuật Toán j j j 1 12 2 8 5 2 6 4 15 1 2 4 12 8 5 6 4 15 1 2 4 5 12 8 6 5 15 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 0 0 i i i 31 32 33 Minh Họa Thuật Toán Độ Phức Tạp Của Thuật Toán Các Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 1 2 3 4 5 6 7 8 4. Shaker Sort 1 2 4 5 6 8 12 15 5. Chèn trực tiếp – Insertion Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 34 35 11. Radix Sort 36 6
Chọn Trực Tiếp – Selection Sort Các Bước Của Thuật Toán Chọn Trực Tiếp Chọn Trực Tiếp – Selection Sort  Ý tưởng:  Chọn phần tử nhỏ nhất trong N phần tử trong  Bước 1: i = 0;  Cho dãy số a: dãy hiện hành ban đầu.  Bước 2: Tìm phần tử a[min] nhỏ nhất trong 12 2 8 5 1 6 4 15  Đưa phần tử này về vị trí đầu dãy hiện hành dãy hiện hành từ a[i] đến a[N]  Xem dãy hiện hành chỉ còn N-1 phần tử của  Bước 3 : Đổi chỗ a[min] và a[i] CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT dãy hiện hành ban đầu  Bước 4 : Nếu i < N-1 thì  Bắt đầu từ vị trí thứ 2; i = i+1; Lặp lại Bước 2;  Lặp lại quá trình trên cho dãy hiện hành... Ngược lại: Dừng. đến khi dãy hiện hành chỉ còn 1 phần tử 37 38 39 Chọn Trực Tiếp – Selection Sort Chọn Trực Tiếp – Selection Sort Chọn Trực Tiếp – Selection Sort i=2 i=0 i=5 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i=3 i=1 i=6 i=4 40 41 42 7
Cài Đặt Thuật Toán Chọn Trực Tiếp Minh Họa Thuật Toán Chọn Trực Tiếp Minh Họa Thuật Toán Chọn Trực Tiếp void SelectionSort(int a[],int n ) { Vị trí nhỏ nhất(0,7) Swap(a[0], a[4]) Vị trí nhỏ nhất(1,7) Swap(a[1], a[1]) int min,i,j; // chỉ số phần tử nhỏ nhất trong dãy hiện hành min min for (i=0; i
Minh Họa Thuật Toán Chọn Trực Tiếp Minh Họa Thuật Toán Chọn Trực Tiếp Độ Phức Tạo Của Thuật Toán  Ðánh giá giải thuật Vị trí nhỏ nhất(5,7) Swap(a[5], a[6]) Vị trí nhỏ nhất(6, 7) n 1 n(n  1) min min soá laàn so saùnh   (n  i)  i 1 2 1 2 4 5 6 12 8 15 1 2 4 5 6 8 12 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 i i 49 50 51 Các Thuật Toán Sắp Xếp Nổi Bọt – Bubble Sort Nổi Bọt – Bubble Sort 1. Đổi chỗ trực tiếp – Interchange Sort  Bước 1 : i = 0; // lần xử lý đầu tiên  Ý tưởng: 2. Chọn trực tiếp – Selection Sort  Bước 2 : j = N-1;//Duyệt từ cuối dãy ngược về vị trí i 3. Nổi bọt – Bubble Sort  Xuất phát từ cuối dãy, đổi chỗ các cặp phần Trong khi (j > i) thực hiện: Nếu a[j]=N-1: Hết dãy. Dừng 8. Heap Sort i. Ngược lại : Lặp lại Bước 2. 9. Quick Sort  Lặp lại xử lý trên cho đến khi không còn cặp 10. Merge Sort phần tử nào để xét. 11. Radix Sort 52 53 54 9
Nổi Bọt – Bubble Sort Nổi Bọt – Bubble Sort Nổi Bọt – Bubble Sort  Cho dãy số a: 2 12 8 5 1 6 4 15 i=0 j=3 i=1 j=5 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i=0 j=6 i=0 j=2 i=1 j=4 i=0 i=4 i=1 j=3 i=0 j=1 55 56 57 Nổi Bọt – Bubble Sort Nổi Bọt – Bubble Sort Cài Đặt Thuật Toán Nổi Bọt void BubbleSort(int a[],int n) i=3 j=5 { i=2 j=5 int i, j; for (i = 0 ; ii ; j --) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i=4 j=6 if(a[j]< a[j-1])// nếu sai vị trí thì đổi chỗ Swap(a[j], a[j-1]); i=2 j=4 } i=5 i=3 j=6 58 59 60 10
Minh Họa Thuật Toán Minh Họa Thuật Toán Minh Họa Thuật Toán j j j 12 1 2 8 5 1 6 4 15 1 2 12 2 8 5 4 6 15 1 2 4 12 4 8 5 6 15 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 0 1 2 3 4 5 6 7 i i i 61 62 63 Minh Họa Thuật Toán Minh Họa Thuật Toán Minh Họa Thuật Toán j j j 1 2 4 12 5 8 5 6 15 1 2 4 5 12 6 8 6 15 1 2 4 5 6 8 12 8 15 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i i i 64 65 66 11
Minh Họa Thuật Toán Độ Phức Tạp Của Thuật Toán Nổi Bọt Các Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort j 3. Nổi bọt – Bubble Sort 1 2 3 4 5 6 7 8 4. Shaker Sort 1 2 4 5 6 8 12 15 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort 67 68 69 Chèn Trực Tiếp – Insertion Sort Chèn Trực Tiếp – Insertion Sort Chèn Trực Tiếp – Insertion Sort  Bước 1: i = 1; //giả sử có đoạn a[1] đã được sắp  Cho dãy số :  Giả sử có một dãy a0 , a1 ,... ,an-1 trong đó i phần  Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong 12 2 8 5 1 6 4 15 tử đầu tiên a0 , a1 ,... ,ai-1 đã có thứ tự. đoạn a[1] đến a[i-1] để chèn a[i] vào  Tìm cách chèn phần tử ai vào vị trí thích hợp của  Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a[i] đoạn đã được sắp để có dãy mới a0 , a1,... ,ai trở CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT nên có thứ tự. Vị trí này chính là vị trí giữa hai  Bước 4: a[pos] = x; //có đoạn a[1]..a[i] đã được sắp i=1 phần tử ak-1 và ak thỏa ak-1 < ai < ak (1≤k≤i).  Bước 5: i = i+1; Nếu i < n : Lặp lại Bước 2 Ngược lại : Dừng i=2 70 71 72 12
Chèn Trực Tiếp – Insertion Sort Chèn Trực Tiếp – Insertion Sort Cài Đặt Thuật Toán Chèn Trực Tiếp void InsertionSort(int d, int n ) { int pos, i; int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử. i=3 for(i=1 ; i= 0)&&(a[pos] > x)) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT {//kết hợp dời chỗ các phần tử sẽ đứng sau x trong dãy i=4 mới a[pos+1] = a[pos]; pos--; } i=7 a[pos+1] = x]; // chèn x vào dãy } i=5 } 73 74 75 Minh Họa Thuật Toán Insertion Sort Minh Họa Thuật Toán Insertion Sort Minh Họa Thuật Toán Insertion Sort Insert a[1] into (0,0) Insert a[2] into (0, 1) pos pos 12 2 8 5 1 6 4 15 2 12 2 8 5 1 6 4 15 2 8 12 8 5 1 6 4 15 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i i x x 76 77 78 13
Minh Họa Thuật Toán Insertion Sort Minh Họa Thuật Toán Insertion Sort Minh Họa Thuật Toán Insertion Sort Insert a[3] into (0, 2) Insert a[4] into (0, 3) Insert a[5] into (0, 4) pos pos pos 2 5 8 12 5 1 6 4 15 12 5 8 12 1 6 4 15 1 2 5 6 8 12 6 4 15 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i i i x x x 79 80 81 Minh Họa Thuật Toán Insertion Sort Minh Họa Thuật Toán Insertion Sort Minh Họa Thuật Toán Insertion Sort Insert a[6] into (0, 5) Insert a[8] into (0, 6) pos pos pos 1 2 4 5 6 8 12 4 15 1 2 4 5 6 8 12 15 1 2 4 5 6 8 12 15 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i i x x 82 83 84 14
Độ Phức Tạp Của Insertion Sort Các Thuật Toán Sắp Xếp Quick Sort 1. Đổi chỗ trực tiếp – Interchange Sort  Ý tưởng: 2. Chọn trực tiếp – Selection Sort  Giải thuật QuickSort sắp xếp dãy a1, a2 ..., aN dựa trên 3. Nổi bọt – Bubble Sort việc phân hoạch dãy ban đầu thành 3 phần : 4. Shaker Sort • Phần 1: Gồm các phần tử có giá trị bé hơn 5. Chèn trực tiếp – Insertion Sort x CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 6. Chèn nhị phân – Binary Insertion Sort • Phần 2: Gồm các phần tử có giá trị bằng x 7. Shell Sort • Phần 3: Gồm các phần tử có giá trị lớn 8. Heap Sort hơn x 9. Quick Sort với x là giá trị của một phần tử tùy ý trong dãy ban 10. Merge Sort đầu. 85 11. Radix Sort 86 87 Quick Sort - Ý Tưởng Quick Sort – Ý Tưởng Quick Sort – Ý Tưởng  Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 đoạn: • 1. ak ≤ x , với k = 1 .. j  Đoạn thứ 2 đã có thứ tự.  Đoạn thứ 2 đã có thứ tự. • 2. ak = x , với k = j+1 .. i-1  Nếu các đoạn 1 và 3 có nhiều hơn 1 phần tử thì dãy CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Nếu các đoạn 1 và 3 chỉ có 1 phần tử : đã có thứ tự ban đầu chỉ có thứ tự khi các đoạn 1, 3 được sắp. • 3. ak  x , với k = i..N  Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc  khi đó dãy con ban đầu đã được sắp. phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày … 88 89 90 15
Giải Thuật Quick Sort Giải Thuật Quick Sort Quick Sort – Ví Dụ  Cho dãy số a:  Bước 1: Nếu left ≥ right //dãy có ít hơn 2 phần tử  Bước 1 : Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc ( l ≤ k ≤ r): 12 2 8 5 Kết thúc; //dãy đã được sắp xếp 1 6 4 15 x = a[k]; i = l; j = r;  Bước 2: Phân hoạch dãy aleft … aright thành các đoạn: aleft.. aj, aj+1.. ai-1, ai.. aright  Bước 2 : Phát hiện và hiệu chỉnh cặp phần tử Đoạn 1  x a[i], a[j] nằm sai chỗ : Phân hoạch đoạn l =0, r = 7: x = a[3] = 5 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Đoạn 2: aj+1.. ai-1 = x  Bước 2a : Trong khi (a[i]x) j--;  Bước 3: Sắp xếp đoạn 1: aleft.. aj 12 2 8 5 1 6 4 15  Bước 4: Sắp xếp đoạn 3: ai.. aright  Bước 2c : Nếu i< j Đoicho(a[i],a[j]);  Bước 3 : Nếu i < j: Lặp lại Bước 2. l=0 r=7 Ngược lại: Dừng 91 92 93 Quick Sort – Ví Dụ Quick Sort – Ví Dụ Quick Sort – Ví Dụ  Phân hoạch đoạn l =0, r = 2:  Phân hoạch đoạn l = 4, r = 7: x = a[2] = 2 x = a[5] = 6 l=0 r=7 l=4 r=7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT l=0 r=2 94 95 96 16
Quick Sort Quick Sort – Ví Dụ  Phân hoạch đoạn l = 6, r = 7: void QuickSort(int a[], int left, int right) Phaân hoaïch daõy { int i, j, x; x = a[6] = 6 x = a[(left+right)/2]; i = left; j = right; while(i < j) i j { 0 1 2 3 4 5 6 7 while(a[i] < x) i++; while(a[j] > x) j--; 12 2 8 5 5 1 6 4 15 if(i
Quick Sort – Ví Dụ Độ Phức Tạp Của Quick Sort Sorting Algorithms  Demo  Animation of sorting algorithms j i  http://math.hws.edu/TMCM/java/xSortLab/ 1 2 3 4 5 6 7 8  http://www.cs.ubc.ca/~harrison/Java/sorting- demo.html 1 2 4 5 6 8 12 15  http://www.cs.uwaterloo.ca/~bwbecker/sortingDemo/ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  http://www2.hawaii.edu/~copley/665/HSApplet.html left right (heap sort) Saép xeáp ñoaïn 3  http://pages.stern.nyu.edu/~panos/java/Quicksort/ (quick sort) 103 104 105 Sorting Algorithms Comparison Bài Tập Average Auxiliary Sort In Method Best Time Worst Time Stability Time Space Place  Nhập một dãy số nguyên n phần tử. Simple Sort (Selection, O(n2) O(n2) / O(n) / O(n2) O(1) Yes Yes  Sắp xếp lại dãy sao cho: Insertion, O(n) Bubble, …)  số nguyên dương đầu ở đầu dãy và (logn) theo thứ tự giảm. Quick Sort O(nlogn) O(nlogn) O(n2) Yes No (stack size) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  số nguyên âm tăng ở cuối dãy và theo Heap Sort O(nlogn) O(nlogn) O(nlogn) O(1) Yes No thứ tự tăng.  số 0 ở giữa. Merge Sort O(nlogn) O(nlogn) O(nlogn) O(n) No Yes  Lưu ý: Không dùng đổi chỗ trực tiếp. Radix Sort O((n+r)k) O((n+r)k) O((n+r)k) O(rk) No Yes 106 107 18