Quick Sorts

Tư tưởng :

Chia để trị và đệ quy

- Cho dãy số ban đầu gồm n phần tử X1,X2,...,Xn chưa được sắp thứ tự .

- Chọn một phần tử Xi tùy ý trong dãy làm chốt .

khi đó dãy S cần xếp được chia thành 3 dãy con

S1= { X/X<chốt }

S2= { X/X=chốt }

S3= { X/X>chốt }

à Như vậy dãy S2 đã được xếp

Tiếp tục xếp hai dãy S1 và S3 theo phương pháp như trên

Thủ tục :

void QuickSort(int X[50],int l,int r)

{

int t=(l+r)/2,tg;

int i=l,j=r;

int chot=X[t];

do

{

while(X[i]<chot) i=i+1;

while(X[j]>chot) j=j-1;

if(i<=j)

{

tg=X[i];

X[i]=X[j];

X[j]=tg;

i++;

j--;

}

} while(i<j);

if(i<r)QuickSort(X,i,r);

if(l<j)QuickSort(X,l,j);

}

Độ phức tạp của thuật toán :

Trung bình : O(nlog2n)

Xấu nhất :O(n2)