Sắp xếp dựa trên phân hoạch quicksort

Quicksort- ý tưởng • Ðể sắp xếp dãy a1, a2, ..., an giải thuật QuickSort dựa trên việc phân hoạch dãy ban đầu thành hai ph ần : • Dãy con 1: Gồm các phần tử a1.. ai có giá trị không lớn hơn x • Dãy con 2: Gồm các phần tử ai .. an có giá trị không nhỏ hơn x • với x là giá trị của một phần tử tùy ý trong dãy ban đầu.
Nội dung trích xuất từ tài liệu:
Sắp xếp dựa trên phân hoạch quicksortSắp xếp dựa trên phân hoạch quicksort Quicksort- ý tưởng• Ðể sắp xếp dãy a1, a2, ..., an giải thuật QuickSort dựa trên việc phân hoạch dãy ban đầu thành hai ph ần :• Dãy con 1: Gồm các phần tử a1.. ai có giá trị không lớn hơn x• Dãy con 2: Gồm các phần tử ai .. an có giá trị không nhỏ hơn x• với x là giá trị của một phần tử tùy ý trong dãy ban đầu. Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 phần:• 1. ak < x , với k = 1..i• 2. ak = x , với k = i..j• 3. ak > x , với k = j..N Quicksort-ý tưởng akx1 I j N• trong đó dãy con thứ 2 đã có thứ tự,• nếu các dãy con 1 và 3 chỉ có 1 phần tử thì chúng cũng đã có thứ tự, khi đó dãy ban đầu đã được sắp.• Ngược lại, nếu các dãy con 1 và 3 có nhiều hơn 1 phần tử thì dãy ban đầu chỉ có thứ tự khi các dãy con 1, 3 được sắp.• Ðể sắp xếp dãy con 1 và 3, ta lần lượt tiến hành việc 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 . Quicksort- giải thuậtGiải thuật phân hoạch dãy al, al+1, ., ar thành 2 dãy con:• 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: x = a[k]; i = l; j = r;• Bước 2 : Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ :• Bước 2a : Trong khi (a[i]x) j--;• Bước 2c : Nếu i< j // a[i] ≥ x ≥ a[j] mà a[j] đứng sau a[i] Hoán vị (a[i],a[j]);• Bước 3 : Nếu i < j: Lặp lại Bước 2.//chưa xét hết mảng Nếu i ≥ j: Dừng Quicksort- nhận xét• Về nguyên tắc, có thể chọn giá trị mốc x là một phần tử tùy ý trong dãy, nhưng để đơn giản, dễ diễn đạt giải thuật, phần tử có vị trí giữa thường được chọn, khi đó k = (l +r)/ 2• Giá trị mốc x được chọn sẽ có tác động đến hiệu quả thực hiện thuật toán vì nó quyết định số lần phân hoạch. Số lần phân hoạch sẽ ít nhất nếu ta chon được x là phần tử median của dãy. Tuy nhiên do chi phí xác định phần tử median quá cao nên trong thực tế người ta không chọn phần tử này mà chọn phần tử nằm chính giữa dãy làm mốc với hy vọng nó có thể gần với giá trị median Quicksort• Giải thuật phân hoạch dãy sắp xếp dãy al, al+1, ., ar:• Có thể phát biểu giải thuật sắp xếp QuickSort m ột cách đệ qui như sau :• Bước 1 : Phân hoạch dãy al . ar thành các dãy con :• - Dãy con 1 : al.. aj ≤ x• - Dãy con 2 : aj+1.. ai-1 = x• - Dãy con 3 : ai.. ar ≥ x• Bước 2 :• Nếu ( l < j ) // dãy con 1 có nhiều hơn 1 phần tử• Phân hoạch dãy al.. aj• Nếu ( i < r ) // dãy con 3 có nhiều hơn 1 phần t ử Phân hoạch dãy ai.. ar Quicksort –ví dụ • Sắp xếp bộ dữ liệu • 1,5,3,6,7,12,4,10,2,9 1 5 3 6 7 12 4 10 2 9Phân hoạch đoạn r=0 r=9, x=a[4]=7 7 0 1 2 3 4 5 6 7 8 9 Quicksort –ví dụPhân hoạch đoạn r=0 r=9, x=a[4]=7 7 1 5 3 6 7 12 4 10 2 9 i j L=0 R=9 1 5 3 6 2 12 4 10 7 9 0 1 2 3 4 5 6 7 8 9 Quicksort –ví dụ Phân hoạch đoạn r=0 r=9, x=a[4]=7 7 1 5 3 6 2 12 4 10 7 9 i j L=0 R=9Phân hoạch đoạn r=0 r=9, x=a[4]=7 j i 1 5 3 6 2 4 12 10 7 9 0 1 2 3 4 5 6 7 8 9 Quicksort –ví dụ 1 5 3 6 2 4 12 10 7 9 Phân hoạch đoạn r=0 r=5, x=a[2]=3L=0 R=5 L=6 R=9 J=i j i 1 2 3 6 5 4 9 7 10 12 0 1 2 3 4 5 6 7 8 9 Quicksort –ví dụ1 2 3 6 5 4 9 7 10 12 …1 2 3 4 5 6 7 9 10 12 Quicksort –cài đặt thuật toánThuật toán QuickSort có thể được cài đặt đệ qui như sau :void QuickSort( int l, int r) { int i,j; int x; x = a[(l+r)/2]; // chọn phần tử giữa làm giá trị mốc i =l; j = r; do { while(a[i] < x) i++; while(a[j] > x) j--; if(i • Class Cmang{• Int []Tappt;• Int spt;• Public void Qsort(){• Quicksort(0,spt-1);• }• Main()• Cmang a;Quicksort-đánh giá thuật toánĐánh giá thuật toán• ...