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

Go down

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

Bài gửi by ASSASSiN on 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

_________________
Hãy REPLY để ủng hộ BOTAY nhé!
avatar
ASSASSiN
♥ Strong Chicken ♥
♥ Strong Chicken ♥

Tổng số bài gửi : 329
Age : 31
Location : Việt Nam
Registration date : 05/10/2007

Xem lý lịch thành viên http://botay.1talk.net

Về Đầu Trang Go down

Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết