Thuật toán sắp xếp: Quick sort

by ASSASSiN Thu Nov 22, 2007 4:55 pm

Thuật toán sắp xếp: Quick Sort

Thuật toán Quick Sort
o Ý tưởng
Ta chọn một phần tử bất kỳ của mảng A giả sử đó là x
Lọc và chia mảng đó thành 3 mảng con:
- mảng A1: A1(i) < x với mọi i
- mảng A2: A2(i) = x với mọi i
- mảng A3: A3(i) > x với mọi i
Sau đó ta lại tiếp tục các bước trên với mảng A1 và A3. Công việc này còn được gọi là phân hoạch nên Quick Sort còn được gọi là sắp xếp theo phương pháp phân hoạch
Giải thuật này sẽ được cài đặt theo phương pháp đệ qui
o Mô tả thuật toán
- Input: Mảng A[1..n]
- Output: Mảng A có thứ tự tăng dần
- Method:

Code:: function quickSort(A, lower, upper){ x = A[(lower + upper) / 2]; i = lower; j = upper; do{ while(A[i] < x) i ++; while (A[j] > x) j --; if (i <= j){ swap(A[i], A[j]); i ++; j --; } }while(i <= j); if (j > lower) quickSort(A, lower, j); if (i < upper) quickSort(A, i, upper); }

o Độ phức tạp tính toán:
Thuật toán Quick Sort tốt nhất trong trường hợp dãy hầu như được sắp xếp và với n khá lớn. Vì vậy ta thường dung Quick Sort trong giai đoạn đầu để phân hoạch, khi đoạn con đủ nhỏ ta sẽ dùng các phương pháp khác để sắp xếp