Thuật toán sắp xếp : QUICK SORT

Ý tưởng

Chọn x là giá trị của một phần tử tùy ý trong dãy ban đầu. Vị trí phần tử thường được chọn là k = (l + r)/2.

Thực hiện phân hoạch với x:

ak < x    

 k = 1..i

ak = x 

 k = i..j

ak > x    

   k = j..N

 

Dãy ban đầu được chia làm 3 phần, trong đó dãy con thứ 2 đã có thứ tự. Dãy ban đầu chỉ có thứ tự nếu dãy con 1 và 3 cũng có thứ tự. Nếu dãy con 1 và 3 chỉ có một phần tử thì chúng đã có thứ tự, ngược lại, ta lần lượt tiến hành phân hoạch từng dãy con theo phương pháp phân hoạch như trên.

 

Giải thuật phân hoạch

            Bước 1: Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, lkr

            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) i++;

                        Bước 2b: Trong khi (a[j] > x) j--;

                        Bước 2c: Nếu i < j                // a[i] ≥ x ≥ a[j] mà a[j] đứng sau a[i]

                                    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 ij: Dừng

 

Giải thuật Quick Sort

            Có thể phát biểu giải thuật sắp xếp Quick Sort một cách đệ qui như sau:      

Bước 1: Phân hoạch dãy a1ar thành các dãy con

                        Dãy con 1:     a1..ajx

                                    Dãy con 1:     aj+1..ai-1 = x

                        Dãy con 1:     ai..arx

            Bước 2:          Nếu (l < j)                  // dãy con 1 có nhiều hơn một phần tử

                                                Phân hoạch dãy a1..aj

                                    Nếu (i < r)                 // dãy con 3 có nhiều hơn một phần tử

                                                Phân hoạch dãy ai..ar

 

Chủ đề liên quan
Thuật toán sắp xếp : QUICK SORT

Cùng chuyên mục

Xem nhiều hôm nay