# data[].attributes.body
#include<stdio.h>
void nhap(int a[], int &n){
int i;
printf("Nhap so luong phan tu: ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("Phan tu %d: ",i);
scanf("%d",&a[i]);
}
}

void in(int a[],int dau, int cuoi)
{
int i;
for(i=dau;i<=cuoi;i++)
printf(" %d ",a[i]);
}

void hoanvi(int &a, int &b){
int tg;
tg=a;
a=b;
b=tg;
}

int vitri_chot(int a[], int dau, int cuoi){
int chot, trai, phai;
chot=a[cuoi];
trai=dau;
phai=cuoi-1;
while(true){
while(trai<=phai&&a[trai]<chot)
trai++;
while(phai>=trai&&a[phai]>chot)
phai--;
if(trai>phai)
break;
hoanvi(a[trai],a[phai]);
trai++;
phai--;
}
hoanvi(a[trai],a[cuoi]);
return trai;
}

void quickSort_cuoi(int a[], int dau, int cuoi){
int vt;
if(dau<cuoi)
{
printf("\nVT=%d Trai=%d Phai=%d :" ,cuoi ,dau ,cuoi-1);
in(a,dau,cuoi);
vt=vitri_chot(a,dau,cuoi);
quickSort_cuoi(a,dau,vt-1);
quickSort_cuoi(a,vt+1,cuoi);
}
}
main(){
int ds[100], spt, x;
nhap(ds,spt);
printf("Day so:              ");
in(ds,1,spt);
quickSort_cuoi(ds,1,spt);
printf("\nDay so sau khi sap xep: \n");
in(ds,1,spt);
}

# data[].attributes.body
- Đầu vào, đầu ra
- Mô tả thuật toán
- Minh họa thuật toán (văn bản)
- Cài đặt thuật toán: chọn phần tử cuối làm chốt

# data[].attributes.body
- Đầu vào: Dãy số (a), số phần tử (n)
- Đầu ra: Dãy số tăng dần

# data[].attributes.body
#include<stdio.h>

void Nhap_mang(int ds[],int n)
{
int i;
for(i=1;i<=n;i++)
{
printf("Nhap phan tu thu %d: ",i);
scanf("%d", &ds[i]);
}
}

void In(int ds[],int n)
{
int i;
for(i=1;i<=n;i++)
printf("%d\t",ds[i]);
}

void quickSort_giua(int ds[], int l , int r)
{
int tg;
if (l <= r)
{
int key = ds[(l+r)/2];
int i = l;
int j = r;

while (i <= j)
{
while (ds[i] < key)
i++;
while (ds[j] > key)
j--;
if (i <= j)
{
tg = ds[i];
ds[i] = ds[j];
ds[j] = tg;
i++;
j--;
}
}
if (l < j)
quickSort_giua(ds, l, j);
if (r > i)
quickSort_giua(ds, i, r);
}
}

main()
{
int *ds,n;
printf("Nhap so luong phan tu cho day so: ");
scanf("%d",&n);
ds = new int [n+1];
Nhap_mang(ds,n);
In(ds,n);
quickSort_giua(ds,1,n);
printf("\n");
In(ds,n);
}

# data[].attributes.body
Dãy số : 5 80 12 90 32 50 71

Quá trình sắp xếp:

Lần 1: {5, 80, 12, 90, 32, 50, 71}

Lần 2: [{5, 12, 32, 50}< 71 <={90, 80}]

Lần 3: [{5,12, 32}< 50 <={∅}] [{∅}< 80 <={90}]

Lần 4: [{5, 12}< 32 <={∅}]

Lần 5: [{5}< 12 <={∅}]

Dãy số được sắp xếp: 5 12 32 50 71 80 90

# data[].attributes.body
#include<stdio.h>
void nhap(int a[], int &n){
int i;
printf("nhap so luong phan tu: ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("a[%d] = ",i);
scanf("%d",&a[i]);
}
}
void in(int a[], int n){
int i;
for(i=1;i<=n;i++)
printf("%d ",a[i]);
}
void hoanvi(int &a, int &b){
int tg;
tg=a;
a=b;
b=tg;
}
int layvitri(int a[], int dau, int cuoi){
int trai, phai, chot;
chot=dau;
trai=dau;
phai=cuoi;
while(trai<phai){
while(a[trai]<=a[chot] && trai < cuoi)
trai++;
while( a[phai]>a[chot] )
phai-- ;
if(trai<phai)
hoanvi(a[trai],a[phai]);
}
hoanvi(a[chot],a[phai]);
return phai;
}
void quicksort_dau(int a[],int dau,int cuoi){
int vt;
if(dau<cuoi){
vt = layvitri(a,dau,cuoi);
quicksort_dau(a,dau,vt-1);
quicksort_dau(a,vt+1,cuoi);
}
}
main(){
int a[100], n, x;
nhap(a,n);
quicksort_dau(a,1,n);
printf("day sau khi sap xep: ");
in(a,n);
}

# data[].attributes.body
- Các cách chọn phần tử chốt
- Minh họa thuật toán (hình ảnh)

# data[].attributes.body
- Cài đặt thuật toán: chọn phần tử đầu làm chốt

# data[].attributes.body
- Cài đặt thuật toán: chọn phần tử giữa làm chốt

# data[].attributes.body
- Chọn phần tử chốt.
- Chia dãy số thành 2 dãy con:
+ Dãy con bên trái phần tử chốt (gồm những phần từ bé hơn hoặc bằng phần tử chốt)
+ Dãy con bên phải phần tử chốt (gồm những phần tử lớn hơn hoặc bằng phần tử chốt)
- Lặp lại thuật toán với 2 dãy con trái và phải
- Kết quả: Dãy số được sắp xếp tăng dần.

# data[].attributes.body
Tốc độ sắp xếp của thuật toán tùy thuộc vào việc lựa chọn phần tử chốt, có một số cách chọn như sau:

1. Chọn phần tử đầu tiên của mảng.

2. Chọn phần tử cuối cùng của mảng.

3. Chọn phần nằm giữa mảng.

4. Chọn Random một phần tử của mảng. (Thuật toán tương tự 3 cách chọn trên)