Thuật toán sắp xếp: Quick Sort (P.2)

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) <>
– 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:

function quickSort(A, lower, upper){
x = A[(lower + upper) / 2];
i = lower;
j = upper;
do{
while(A[i] <>
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 <>
quickSort(A, i, upper);
}

o Độ phức tạp tính toán: O(nlnn)

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

,

  1. Để lại bình luận

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: