Quick Sort - Details, research.

                                                Quick Sort

while(arr[j] > pivot){

                                               

                                                j--;

                                               

                                    }

                                   

while(arr[i] < pivot){

                                               

                                                i++;

                                               

                                    }

Với hai lệnh trên, thì ta đảm bảo được từ vị trí j đến r các phần tử luôn lớn hơn pivot, các phần tử từ l đến i luôn nhỏ hơn pivot

- Nhưng có một thắc mắc là nếu giả sử khi i gặp phần tử bằng pivot, j gặp phần tử nhỏ hơn pivot ở bên phải, theo các câu lệnh sau thì nó được tráo đổi:

            if(i <= j){

                                               

                                                tmp = arr[i];

                                                arr[i] = arr[j];

                                                arr[j] = tmp;

                                                j--;

                                                i++;

                                               

                                    }

Vậy sau khi hoán đổi xong j giảm, i tăng nhưng ở giữa khoảng i, j còn có một phần tử lớn hơn pivot thì ta làm cách nào để tráo để đưa phần tử đó về sau pivot (tức là thuộc nhóm các phần tử lớn hơn pivot). (TM1)

Ta có toàn bộ code của Quick Sort:

void quickSort(int arr[], int l, int r){

           

           

                       

                        int i = l;

                        int j = r;

                        int pivot = arr[r];

                        int tmp;

                       

                        while(i <= j){

                                   

                                    while(arr[j] > pivot){

                                               

                                                j--;

                                               

                                    }

                                   

                                    while(arr[i] < pivot){

                                               

                                                i++;

                                               

                                    }

                                   

                                    if(i <= j){

                                               

                                                tmp = arr[i];

                                                arr[i] = arr[j];

                                                arr[j] = tmp;

                                                j--;

                                                i++;

                                               

                                    }

                        }

                       

                        if(l < j){

                                   

                                    quickSort(arr, l, j);

                                   

                        }

                       

                        if(r > i){

                                   

                                    quickSort(arr, i, r);

                                   

                        }

           

}
Ta nhận thấy cứ sau một vòng while lớn thoát ra thì lại có một vị trí pivot được đặt vào vị trí cuối cùng của nó. Như vậy nếu TM2 là hợp lý thì rõ ràng Quick Sort này sẽ sai vì pivot đã cố định, hơn nữa đệ quy đằng sau chỉ trong 2 khoảng phân cách bởi nó nên không còn cơ hội để tráo lại phần tử lớn hơn pivot đó đưa lên trên pivot.

Ta có pivot đang ở giữa mảng.
Phân tích cách hoạt động của Quick sort trong mảng:
1 9 6 4 0 5 2 8 3 7 9

Vị trí của i là tại phần tử bằng 1, vị trí của j là tại phần tử bằng 9, pivot tại phần tử bằng 5.
B1: duyệt i đến phần tử lớn hơn pivot = 5. Tức là tại phần tử = 9. Duyệt j xuống phần tử nhỏ hơn 5 tức 3
B2 tráo vị trí 2 thằng này được mảng mới:
1 3 6 4 0 5 2 8 9 7 9
Lúc này, i tại vị trí phần tử bằng 6, j tại vị trí phần tử bằng 8 .
Lặp lại
B1 thấy tại i phân tử lớn hơn pivot nên dừng ở đó đợi tráo đổi. j duyệt đến 2 nhỏ hơn , ra ngoài tráo đổi với phần tử tại i. Được mảng mới:
1 3 2 4 0 5 6 8 9 7 9.
Dãy này đã thỏa mãn : các phần tử bên trái pivot nhỏ hơn pivot, các phần tử bên phải thì lớn hơn.

Trở lại với thắc mắc 1 (TM1):

Giả sử khi i gặp phần tử là pivot, j gặp phần tử nhỏ hơn pivot ở bên phải, theo các câu lệnh tráo đổi thì nó được tráo đổi. Vậy sau khi hoán đổi xong j lại giảm, i tiếp tục tăng nhưng ở giữa khoảng i, j còn có một phần tử lớn hơn pivot thì ta làm cách nào để tráo để đưa phần tử đó về sau pivot (tức là thuộc nhóm các phần tử lớn hơn pivot). Bây giờ ta phải chứng minh không có TH này xảy ra.
Dễ thấy ở đây pivot ở giữa mảng, như vậy khi i duyệt đến giữa gặp thằng pivot thì trong đoạn đường nó đi, các phần tử đều nhỏ hơn pivot rồi. Ta xét tiếp, lúc này j đang đợi ở phần tử nhỏ hơn, thầy i gặp được pivot (không tm arr[i] < pivot) thì tráo đổi. j tiếp tục duyệt tiếp thì nếu ở giữa i, j còn phần tử lớn hơn pivot thì sao?

Đến đây ta nhìn lại đoạn này:
if(l < j){

                                   

                                    quickSort(arr, l, j);

                                   

                        }

                       

                        if(r > i){

                                   

                                    quickSort(arr, i, r);

                                   

                        }

2 đệ qui của quickSort về sau ko liên quan gì đến pivot cả và duyệt tiếp từ i, j đến r, l và pivot lại bị duyệt lần nữa, vậy tất cả các kĩ thuật mà ta nghĩ áp dụng vào bài toàn này từ đầu là sai.
Đoạn code copy trên mạng mà ta đang phân tích trên là một biến thể của quickSort, không theo kĩ thuật, sau một lần lặp là pivot ở vị trí cuối cùng của nó và lại sắp xếp 2 nửa chỉ lớn hơn và chỉ nhỏ hơn ở hai bên của nó thì ta được dãy sắp xếp.

=> Vấn đề ở đây là hàm đệ qui. nên có thể thuật toán vẫn phù hợp

Vậy ta cùng phân tích theo hướng đi của thuật giải này:
Đến khi i, j gặp nhau và thoát ra khỏi vòng lặp thì lúc này i – j == 1 vì i gặp các phần tử lớn hơn pivot do j thuần hóa, còn j gặp các phần tử nhỏ hơn pivot do i thuần hóa. Thoát ra khỏi vòng lặp, nên từ l đến j là các phần tử nhỏ hơn pivot còn từ i đến r là các phần tử lớn hơn hoặc bằng pivot, vậy tiếp tục với các qui trình trên kết hợp với recursion (đệ qui) thì ta được dãy sắp xếp. Hay nói cách khác j là điểm kết thúc của lãnh thổ, mà lãnh thổ này đã được thuần hóa bởi i gồm các phần tử nhỏ hơn pivot. Còn i thì là điểm đầu tiên, vì vừa bước chân đến lãnh thổ của j đã được j thuần hóa gồm các phần tử lớn hơn pivot. Cứ đệ qui như vậy

- Bây giờ ta cũng đã hiểu thêm được công dụng của kiểm tra điều kiện if(i <= j){ trong khối lệnh kiểm tra để gán là nếu i > j mà tiếp tục tráo đổi thì sai vì j lúc này đi vào lãnh thổ đã sắp xếp của i, còn i đi vào lãnh thổ đã sắp xếp của j , nếu ko có điều kiện trên, 2 thằng này tráo đổi nhau thì sẽ phá hỏng quy luật đã sắp xếp của hai lãnh thổ.

- Tiếp theo ta xet hai điều kiện này :     while(arr[i] < pivot) và     while(arr[j] > pivot) nếu mà ở 2 về gặp phần tử bằng pivot thì nó đều đổi, như vậy liệu có xảy ra th ở 2 bên của 2 lãnh thổ đều có phần tử bằng pivot ko đc sắp xếp ko. Ta nhận thấy từ l đến j là các phần tử <= pivot, từ i đến r là các phần tử >= pivot nên ở lãnh thổ đầu tiên (<= pivot) thì nếu có các phần tử bằng pivot thì đẩy xuống cuối, còn ở lãnh thổ thứ 2 (>= pivot) các phần tử bằng pivot đẩy lên đầu như vậy câu trả lời là ko vì các phần tử = pivot sẽ được đẩy lại gần nhau.

Nhận xét 1 :
Nếu trong if(i <= j){

                                               

                                                tmp = arr[i];

                                                arr[i] = arr[j];

                                                arr[j] = tmp;

                                                j--;

                                                i++;

                                               

                                    }

mà không có j--; i++; sẽ xảy ra vòng lặp vô hạn vì arr[i] và arr[j] lúc này luôn ko thể tăng lên được vì luôn ko tm 2 vòng lặp trước đó.

2. Có thể bỏ dấu “=” trong điều kiện vòng while ngoài cùng while(i <= j); vì th i = j và th i==j trong thân vòng lặp chỉ xét khi arr[i] == arr[j] thì vẫn tăng i++; giảm j--;

ra ngoài thân vòng lặp i – j == 1 <= Sai , lý luận này sai vì trong th j – i == 1 nhảy vào trong câu lệnh if trong while sau đó tráo đổi phần tử tại i và j cho nhau i++; j—ra ngoài i==j. Không thỏa mãn while => thoát while . Nhưng ra ngoài quickSort 2 nửa còn lại vẫn đúng vì sort 2 nửa có đầu nửa này là đít nửa kia vần thỏa mãn đk sau khi sort xong.
Như vậy thì ta có thể thay thế j trong phần đệ qui là i – 1; Tức là 2 nửa của i. Phần tử tại i lúc này là điểm phân hoạch

Với một số tài liệu thì nó sẽ tạo riêng hàm tìm phần tử pivot làm chốt t/m là:
Nếu mảng toàn các phần tử giống nhau => không có chôt => đã sắp xếp.
Nếu mảng có 2 phần tử khác nhau. Lúc đầu, nó cho phần tử đầu tiên làm pivot sau đó đi tìm phần tử kế tiếp đầu tiên mà khác nó. Nếu phần tử đó lớn hơn pivot thì gán pivot cho phần tử đó, ngược lại thì giữ nguyên. Tức là tìm phần tử lớn nhất trong hai phần tử khác nhau đầu tiên. Tại sao lại là lớn nhất? Mà theo phân tích thì nhỏ hơn và lớn hơn đều được
=> Cải tiển này rất chính xác. Nếu không thêm cách tìm chốt này mà giữ nguyên cách trên, ta thấy nếu phần tử đầu tiên là min trong mảng thì quá trình duyệt i, j thì j không tìm được phần tử nhỏ hơn min cho đến khi gặp min.
- Nhận xét 3: pivot như là một chốt trong lần lặp đầu tiên để i, j không đi ra khỏi mảng. Hơn thế nữa, vùng lãnh thổ do i, j thuần hóa trong quá trình lặp cũng là chốt cho j, i để tránh lặp không cần thiết.

Độ phức tạp trong Qick Sort là O(nlogn).