Tài liệu Cấu trúc dữ liệu di động chuong 2

ĐẠI HỌC QUỐC GIA TPHCM TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CHƯƠNG II TÌM KIẾM VÀ SẮP XẾP Nguyễn Trọng Chỉnh 1 [email protected] GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT PHƯƠNG PHÁP MERGE SORT PHƯƠNG PHÁP RADIX SORT (Sinh viên tự đọc) 2 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT * Ý tưởng:(Quick sort - sắp xếp dựa trên phân hoạch) Giả sử dãy A có n phần tử có thứ tự tăng dần. - Phần tử chốt (pivot) ak, k = 0,..,n-1 có giá trị khóa không nhỏ hơn các phần tử của dãy đã có thứ tự a0,..,ak-1 và có giá trị khóa không lớn hơn các phần tử của dãy đã có thứ tự ak+1,..an-1. - Để sắp xếp, chọn một phần tử ak bất kỳ trong A, chia dãy A thành hai dãy a0,..,ak-1 có giá trị không lớn hơn ak và dãy ak+1,..,an-1 có giá trị không nhỏ hơn, sắp xếp hai dãy này theo cách như trên. 3 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT * Giải thuật: Sử dụng giải thuật đệ quy như sau: Đầu vào: dãy al,al+1,..,ar chưa có thứ tự. Đầu ra: dãy al, al+1,..,ar có thứ tự tăng dần. - B1: Nếu l < r thì k  (l + r)/2, x  ak, i  l, j  r; ngược lại qua B6. - B2: Nếu ai > x, qua B3; ngược lại i  i+1, qua B2. - B3: Nếu aj < x, qua B4; ngược lại j  j - 1, qua B3. - B4: Nếu i < j thì hoán đổi ai và aj. - B5: Thực hiện Quick Sort cho dãy al, al+1,..,ar=j và al=i, ai+1,..,ar - B6: Kết thúc. 4 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT * Cài đặt: void QuickSort(int *a, int l, int r) { int i, j, x; if (l >= r) return; x = a[(l+r)/2]; i = l; j = r; while(i < j) { while (a[i] < x) i++; while (a[j] > x) j--; if (i <= j) {hoandoi(a[i], a[j]); i++; j--; } } QuickSort(a, l, j); QuickSort(a, i, r); } 5 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=0 Tìm i 7 x=1 5 8 i=0 l=0 Tìm j 7 7 i=0 4 2 6 5 8 1 4 2 6 8 1 3 j=7 r=7 x=1 5 3 j=7 r=7 x=1 i=0 l=0 Tìm j 1 r=7 4 2 6 j=6 3 6 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=0 Tìm j 7 x=1 5 8 i=0 l=0 Tìm j 7 7 i=0 4 2 6 3 j=5 x=1 5 8 1 r=7 4 2 6 3 j=4 i=0 l=0 Tim j 1 r=7 x=1 5 8 1 j=3 r=7 4 2 6 3 7 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=0 5 8 i=1 Tìm i 1 x=1 j=2 l=0 1 5 8 1 2 6 7 3 r=7 j=2 l=0 Tìm j 4 x=1 i=1 Tìm j 7 r=7 4 2 6 x=1 5 i = 1, j = 1 8 7 3 r=7 4 2 6 3 8 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=0 r=0 chia dãy con l=1 1 5 x=1 8 7 r=7 4 2 6 3 i=1 j=0 l=0 r=0 Xếp dãy trái Xếp dãy phải Tìm i 1 l=1 5 i=1 x=4 8 7 4 r=7 2 6 3 9 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=1 Tìm j 5 x=4 8 7 i=1 l=1 Tìm i 3 4 r=7 2 x=4 8 7 4 2 6 x=4 8 i=2 5 j=6 l=1 3 3 j=7 r=7 i=2 Tìm j 6 7 4 r=7 2 6 j=6 5 10 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=1 Tìm j 3 x=4 8 7 4 i=2 3 2 7 4 2 5 r=7 j=4 x=4 l=1 3 6 x=4 i=3 Tìm j 2 j=5 l=1 Tìm i r=7 4 7 i=3 j=4 8 6 5 r=7 8 6 5 11 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=1 Tìm i 2 4 7 i=4 x=2 j=3 r=3 3 2 4 l=1 xếp dãy trái l=4 l=1 chia dãy con r=3 x=2 r=3 3 2 4 3 i=1 r=7 8 6 5 j=3 12 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=1 Tìm j x=2 r=3 3 2 4 i=1 l=1 x=2 Tìm j 3 2 j=3 r=3 4 i=1 j=2 l=1 l=2 r=3 r=1 chia dãy con 2 3 j=1 i=2 4 13 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=1 xếp dãy trái r=1 2 l=2 x=3 Tìm i 3 4 l=2 x=3 xếp dãy phải r=3 r=3 3 4 i=2 14 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=2 x=3 4 j=3 l=2 x=3 Tìm j 3 i=2 Tìm j r=3 r=3 3 4 i=2 j=3 15 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=2 3 chia dãy con j=1 Xếp dãy phải r=3 4 i=3 l=3 r=3 4 l=4 Xếp dãy phải x=8 7 8 r=7 6 5 16 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=4 Tìm i x=8 7 8 r=7 6 i=4 l=4 x=8 Tìm j 7 8 l=4 Tìm i 8 j=7 r=7 i=5 x=8 7 i=5 5 6 5 j=7 r=7 6 5 j=7 17 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=4 Tìm i x=8 7 5 r=7 6 8 i=6 j=6 l=4 Tìm i x=8 7 5 r=7 6 8 j=6 i=7 l=4 Tìm j x=8 7 5 r=7 6 8 j=6 i=7 18 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORTl = 7 l=4 Chia dãy con 7 r=6 5 6 r=7 8 j=6 i=7 l=4 Xếp dãy trái 7 l=4 Tìm i 7 i=4 x=5 r=6 5 6 x=5 r=6 5 6 19 GIẢI THUẬT SẮP XẾP PHƯƠNG PHÁP QUICK SORT l=4 Tìm i 7 x=5 r=6 5 6 i=4 l=4 Tìm j 7 i=4 l=4 Tìm j x=5 r=6 5 6 j=6 x=5 r=6 7 5 i=4 j=5 6 20