tailieunhanh - Quick Sort

Tham khảo tài liệu quick sort , công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Quick Sort Ý tưởng: Giải thuật QuickSort sắp xếp dãy a1, a2 ., aN dựa trên việc phân hoạch dãy ban đầu thành 3 phần : • Phần 1: Gồm các phần tử có giá trị bé hơn x • Phần 2: Gồm các phần tử có giá trị bằng x • Phần 3: Gồm các phần tử có giá trị lớn 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 đoạn: • 1. ak ≤ x , với k = 1 j • 2. ak = x , với k = j+1 i-1 • 3. ak ³ x , với k = iN Ak =x Đoạn thứ 2 đã có thứ tự. Nếu các đoạn 1 và 3 chỉ có 1 phần tử : đã có thứ tự khi đó dãy con ban đầu đã được sắp. Ak =x Đoạn thứ 2 đã có thứ tự. Nếu các đoạn 1 và 3 có nhiều hơn 1 phần tử thì dãy ban đầu chỉ có thứ tự khi các đoạn 1, 3 được sắp. Để sắp xếp các đoạn 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 Giải Thuật Quick Sort Bước 1: Nếu left ≥ right //dãy có ít hơn 2 phần tử Kết thúc; //dãy đã được sắp xếp Bước 2: Phân hoạch dãy aleft aright thành các đoạn: aleft aj, aj+1 ai-1, ai aright Đoạn 1 £ x Đoạn 2: aj+1 ai-1 = x Đoạn 3: ai aright ³ x Bước 3: Sắp xếp đoạn 1: aleft aj Bước 4: Sắp xếp đoạn 3: ai aright Giải Thuật Quick Sort 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) j--; if(i <= j) { Swap(a[i],a[j]); i++ ; j--; } } while(i <= j); if(left