Quick Sort

Thuật toán Quick Sort

–    Nếu mảng A rỗng hoặc chỉ có một phần tử thì trả về chính A (đã có thứ tự).

–    Ngược lại chọn một phần tử x bất kỳ của A, chia A thành 3 mảng:

+ L: chứa các phần tử của A nhỏ hơn x

+ E: chứa các phần tử của A bằng x

+ G: chứa các phần tử của A lớn hơn x

–    Sắp xếp một cách đệ qui hai mảng con L và G

–    Tạo mảng A bằng cách liên tiếp 3 mảng L, E, G theo thứ tự.

1.Ý tưởng:

Chọn ngẫu nhiên một phần tử X

Duyệt dãy từ bên trái (theo chỉ số i) trong khi còn ai < x

Duyệt dãy từ bên phải (theo chỉ số j) trong khi còn aj > x

Đổi chỗ ai và ạ nếu hai phía chưa vượt qua nhau

Tiếp tục quá trình duyệt và đổi chổ như trên trong khi hai phía còn chưa vượt qua nhau( tức là còn có i<=j)

Kết quả phân hoạch dãy thành 3 phần:

a_k<=x với k=1,…j (dãy con thấp)

a_m>=x với m=I,…,n (dãy con cao);

a_{h=x với} h=j+1,…i-1

      Thuật toán thể hiện ý tưởng đệ quy và chia để trị.

2. Thuật toán:

Thuật toán quicksort:

Input: a[1..n]

Output a[1..n] không giảm

Mô tả thuật toán:

Quick sort(a,n)=QS(a,1,n)

-         thuật toán phân hoach

input: a[1..n],1,r

output: a[1..r] tăng dần

mô tả:

QS(a,1,r)

I=1;

J=r;

X=a[(1+r)/2];

Do

{

      While(a[i]<x)

                  I++;

      While(a[j]>x)

                  j--;

      if (i<=j)

      {

                  Đổi chổ a[i] và a[j];

                  I++;

                  j--;

      }

}

While(i<=j);

If (1<=j)

      QS(a,1,j);

If(r>i)

      QS(a,I,r);

3. mã nguồn bằng C:

#include<stdio.h>   

#include<conio.h>

Void quicksort()

{

Int I,j,x,t,r;

I=q;

J=r;

X=a[(q+r)/2;

Do

{

            While (a[i]<x)

                        i++;

While (a[j]>x)

                        j--;

ì(i<=j)

{

            T=a[i];

            a[i]=a[j];

            a[j]=t;

            i++;

            j--;

}

}

While i<j

     If (q<j)

     Quicksort(q,j);

     Ì (i<r)

     Quicksort (I,r);

}