TAILIEUCHUNG - 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. | 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. 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 = jN Quicksort-ý tưởng 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 . akx 1 I j N Quicksort- giải thuật Giả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 x , với k = jN Quicksort-ý tưởng 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 . akx 1 I j N Quicksort- giải thuật Giải thuật phân hoạch dãy al, al+1, ., ar thành 2 dãy
đang nạp các trang xem trước
