# data[].attributes.body
Input:  dãy số (a), số phần tử (n)
Output:  dãy số tăng dần

# data[].attributes.body
Input:ds(a)spt(n)
Output:ds tăng dần

# data[].attributes.body
Input: Dãy số (a), số phần tử (n)
Output: Dãy số tăng dần

# data[].attributes.body
Input: dãy a, số phần tử n
Output: dãy số tăng dần

# data[].attributes.body
Input: Dãy số (a), số phần tử (n)
Output: Dãy số tăng dần

# data[].attributes.body
- Thuật toán phân đoạn: Đặt chốt là phần tử cuối cùng của dãy số a
+ Bắt đầu từ phần tử trái nhất của dãy số a có chỉ số là left
+ Phần tử phải nhất của dãy số a có chỉ số là right - 1 (bỏ qua phần tử chốt)
+ Chừng nào left < right mà a[left] > chốt và a[right] < chốt thì hoán vị a[left] và a[right] cho nhau
+ Sau cùng, hoán vị a[left] và chốt cho nhau
-> Khi đó, a[left] đã đứng đúng vị trí và chia dãy số làm đôi (bên trái và bên phải)
- Sắp xếp: Khi đã có 2 mảng con (mảng bên trái và mảng bên phải). Tiếp tục công việc với mỗi mảng con (chọn chốt -> phân đoạn) cho tới khi mảng được sắp xếp

# data[].attributes.body
1. Chọn phần tử chốt.

Có 4 cách chọn phần tử chốt
+ Chọn phần tử đứng đầu danh sách làm phần tử chốt
+ Chọn phần tử đứng cuối danh sách làm phần tử chốt
+ Chọn phần tử đứng giữa danh sách làm phần tử chốt
+ Chọn phần tử ngẫu nhiên làm phần tử chốt
2. Khai báo 2 biến con trỏ để trỏ để duyệt 2 phía của phần tử chốt
3. Biến bên trái trỏ đến từng phần tử mảng con bên trái của phần tử chốt
4.  Biến bên phải trỏ đến từng phần tử mảng con bên phải của phần tử chốt
5. Khi biến bên trái lớn hơn phần tử chốt thì di chuyển sang bên phải
6.  Khi biến bên phải nhỏ hơn phần tử chốt thì di chuyển sang bên trái
7. Nếu không xảy ra 2 trường hợp 5 và 6 thì tráo đổi giá trị 2 bên trái và phải
8. Nếu trái lớn hơn phải thì đây là giá trị chốt mới

# data[].attributes.body
·        Mô tả thuật toán:

1.           Chọn phần tử chốt có 3 cách :

-Cách 1 : Chọn phần tử đầu trong thuật toán Quick Sort

-Cách 2 : Chọn phần tử cuối

-Cách 3 : Chọn phần tử giữa trong thuật toán Quick Sort

2.           Khai báo 2 biến con trỏ để trỏ để duyệt 2 phía của phần tử chốt.

3.           Biến bên trái trỏ đến từng phần tử mảng con bên trái của phần tử chốt.

4.           Biến bên phải trỏ đến từng phần tử mảng con bên phải của phần tử chốt.

5.           Khi biến bên trái nhỏ hơn phần tử chốt thì di chuyển sang phải.

6.           Khi biến bên phải nhỏ hơn phần tử chốt thì di chuyển sang trái.

7.           Nếu không xảy ra trưởng hợp 5 và 6 thì tráo đổi giá trị 2 biến trái và phải.

8.           Nếu trái lớn hơn phải thì đây là giá trị chốt mới.

# data[].attributes.body
1.Chọn phần tử chốt có 3 cách chọn:

- Chọn phần tử đầu

- Chọn phần tử cuối

- Chọn phần tử giữa

2.Khai báo 2 biến con trỏ để duyệt về hia phía

3.Biến bên trái đến các mảng con phía bên trái của phần tử chốt

4.Biến bên phải đến từng mảng con bên phải của phần tử chốt

5 Khi biến bên trái nhỏ hơn phần tử chốt thì di chuyển sang phải.

6. Khi biến bên phải nhỏ hơn phần tử chốt thì di chuyển sang trái.

7. Nếu không xảy ra trưởng hợp 5 và 6 thì tráo đổi giá trị 2 biến trái và phải.

8. Nếu trái lớn hơn phải thì đây là giá trị chốt mới.

# data[].attributes.body
#include <stdio.h>
int n;
void nhap(int *a) {
int i;
for(int i = 1; i <= n; i++) {
printf("So thu %2d: " ,i);
scanf("%d", &a[i]);
}
}

void xuat(int *a) {
int i;
for(i = 1; i <= n; i++)
printf("%2d ", a[i]);
}

void hoanvi(int &x, int &y) {
int tg;
tg = x;
x = y;
y = tg;
}

int phandoan(int *a, int low, int high) {
int chot, left, right;
chot = a[high];
left = low;
right = high - 1;
while(true) {
while(left <= right && a[left] < chot)
left++;
while(left <= right && a[right] > chot)
right--;
if(left >= right)
break;
printf("\nChot= %2d     Left= %2d <-> Right= %2d : ", a[high], a[left], a[right]);
hoanvi(a[left], a[right]);
xuat(a);
left++;
right--;
}
printf("\nChot= %2d <-> Left= %2d               : ", a[high], a[left]);
hoanvi(a[left], a[high]);
xuat(a);
return left;
}

void quicksort(int *a, int low, int high) {
int x;
if(low < high) {
x = phandoan(a, low, high);
quicksort(a, low, x - 1);
quicksort(a, x + 1, high);
}
}

main() {
int *a;
printf("Nhap bao nhieu so: ");
scanf("%d" , &n);
a = new int[n + 1];
nhap(a);
printf("Day so\n");
xuat(a);
printf("\nQuy trinh sap xep");
quicksort(a, 1, n);
printf("\nDay so da sap xep\n");
xuat(a);
}

# data[].attributes.body
Dãy số
14   20   16   4   13   10   15    8   6
Quá trình sắp xếp
Chọn giá trị 13 làm chốt
4   10   8   6    13    14     20    16    15
Chọn 8,16 làm chốt
4   6   8   10    13    14     15    16    20
Chọn 6,10,15,20 làm chốt
4   6   8   10    13    14     15    16    20
Chọn 4,14 làm chốt
4   6   8   10    13    14     15    16    20

# data[].attributes.body
Xét                               12,   24,   17,    4,    11,   10,    15,   8,    7

L<=chốt,R >=chốt      12,   24,  17,    4,    11,   10,    15,   8,   7

11 làm chốt                  4,     10,    8,    7,     11,   12,   24,  17,   15

8,17 làm chốt              4,      7,      8,    10,   11,   12,   15,  17,  24

7,10,15,21 làm chốt    4,     7,      8,   10,   11,   12     15,   17,   24

4,12 làm chốt              4,      7,     8,    10,   11,   12,   15,  17,   24
Dãy sau khi sắp xếp là : 4,  7,     8,    10,   11,   12,   15,  17, 24

# data[].attributes.body
Xét dãy số                    5, 16, 8, 11, 10, 2, 7, 19, 13
11 làm chốt                  5, 8, 2, 7, 10, 16, 11, 19, 13
8,19 làm chốt              5, 2, 7, 8, 10, 16, 11, 13, 19
2,7,11,13 làm chốt        5, 2, 7, 8, 10, 16, 11, 13, 19
5,16 làm chốt              2, 5, 7, 8, 10, 11, 13, 16, 19
Kết quả : 2, 5, 7, 8, 10, 11, 13, 16, 19

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

void swap(int &a, int &b)

{

int t = a;

a = b;

b = t;

}

int partition (int arr[], int low, int high)

{

int pivot = arr[high];    // pivot

int left = low;

int right = high - 1;

while(true){

while(left <= right && arr[left] < pivot) left++;

while(right >= left && arr[right] > pivot) right--;

if (left >= right) break;

swap(arr[left], arr[right]);

left++;
right--;

}

swap(arr[left], arr[high]);

return left;

}

void quickSort(int arr[], int low, int high)

{

if (low < high)

{

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}

}
void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

}

int main()

{

int arr[] = {14,20,16,4,13,10,15 ,8 ,6};

int n = sizeof(arr)/sizeof(arr[0]);

quickSort(arr, 0, n-1);

printf("Sorted array: \n");

printArray(arr, n);

return 0;

}

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

void HoanVi(int &a, int &b)

{

int t = a;

a = b;

b = t;

}

//  phân đoạn trong mảng

int partition (int a [], int low, int high)

{

int pivot = a [high];    // khai báo phần tử đánh dâu pivot

int left = low;   //khai báo biến bên trái

int right = high - 1; //khai báo biến bên phải

while(true){

while(left <= right && a [left] < pivot) left++; // tìm phần tử >= phần tử pivot trong mảng

while(right >= left && arr[right] > pivot) right--; // tìm phần tử <= phần tử pivot trong mảng

if (left >= right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp

HoanVi(a [left], a [right]); // nếu chưa xong thì sử dụng hàm HoanVi() để tráo đổi.

left++; // Vì left hiện tại đã xét, nên cần tăng

right--; // Vì right hiện tại đã xét, nên cần giảm

}

HoanVi(a [left], a [high]);

return left; // Trả về chỉ số sẽ dùng để chia đôi mảng

}

/* Hàm thực hiện giải thuật quick sort */

void quickSort(int a [], int low, int high)

{

if (low < high)

{

int index = partition(a, low, high);

// Gọi đệ quy sắp xếp 2 mảng con trái và phải

quickSort(a, low, index - 1);

quickSort(a, index + 1, high);

}

}

void printArray(int a [], int size)

{

int i;

for (i=0; i < size; i++){

Printf(“a[i]=”,i);

Printf(“\t”);

}

}

int main()

{

int ds[] = { 12,   24,   17,    4,    11,   10,    15,   8,    7};

int n = sizeof(a)/sizeof(a[0]);

quickSort(a, 0, n-1);

Printf ("Mảng sau khi được sắp xếp: \n");

printArray(a, n);

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

void swap(int &a, int &b)

{

int t = a;

a = b;

b = t;

}

int partition (int arr[], int low, int high)

{

int pivot = arr[high];    // pivot

int left = low;

int right = high - 1;

while(true){

while(left <= right && arr[left] < pivot) left++;

while(right >= left && arr[right] > pivot) right--;

if (left >= right) break;

swap(arr[left], arr[right]);

left++;

right--;

}

swap(arr[left], arr[high]);

return left;

}

void quickSort(int arr[], int low, int high)

{

if (low < high)

{

int pi = partition(arr, low, high);

// Gọi đệ quy sắp xếp 2 mảng con trái và phải

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}

}

/* Hàm xuất mảng */

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

}

int main()

{

int arr[] = {  5, 16, 8, 11, 10, 2, 7, 19, 13 };

int n = sizeof(arr)/sizeof(arr[0]);

quickSort(arr, 0, n-1);

printf("Sorted array: \n");

printArray(arr, n);

return 0;

}

# data[].attributes.body
- Phan Quang Nhã
+ STT - 39
+ MSV - 2050531200240
- Lương Hàn Nhật
+ STT - 41
+ MSV - 2050531200244
- Lê Anh Quốc (Nhóm trưởng)
+ STT - 50
+ MSV - 2050531200262
- Trần Hữu Tiến Đạt
+ STT - 68
+ MSV - 2050531200128

# data[].attributes.body
*Thuật toán gồm hai giai đoạn: Phân đoạn mảng và Sắp xếp

- Thuật toán phân đoạn: Đặt chốt là phần tử cuối cùng của dãy số a
+ Bắt đầu từ phần tử trái nhất của dãy số a có chỉ số là left
+ Phần tử phải nhất của dãy số a có chỉ số là right - 1 (bỏ qua phần tử chốt)
+ Chừng nào left < right mà a[left] > chốt và a[right] < chốt thì hoán vị a[left] và a[right] cho nhau
+ Sau cùng, hoán vị a[left] và chốt cho nhau
-> Khi đó, a[left] đã đứng đúng vị trí và chia dãy số làm đôi (bên trái và bên phải)

- Sắp xếp: Khi đã có 2 mảng con (mảng bên trái và mảng bên phải). Tiếp tục công việc với mỗi mảng con (chọn chốt -> phân đoạn) cho tới khi mảng được sắp xếp (Đệ quy)

# data[].attributes.body
#include <stdio.h>
int n;
void nhap(int *a) {
int i;
for(int i = 1; i <= n; i++) {
printf("So thu %2d: " ,i);
scanf("%d", &a[i]);
}
}

void xuat(int *a) {
int i;
for(i = 1; i <= n; i++)
printf("%2d ", a[i]);
}

void hoanvi(int &x, int &y) {
int tg;
tg = x;
x = y;
y = tg;
}

int phandoan(int *a, int low, int high) {
int chot, left, right;
chot = a[high];
left = low;
right = high - 1;
while(true) {
while(left <= right && a[left] < chot)
left++;
while(left <= right && a[right] > chot)
right--;
if(left >= right)
break;
printf("\nChot= %2d     Left= %2d <-> Right= %2d : ", a[high], a[left], a[right]);
hoanvi(a[left], a[right]);
xuat(a);
left++;
right--;
}
printf("\nChot= %2d <-> Left= %2d               : ", a[high], a[left]);
hoanvi(a[left], a[high]);
xuat(a);
return left;
}

void quicksort(int *a, int low, int high) {
int x;
if(low < high) {
x = phandoan(a, low, high);
quicksort(a, low, x - 1);
quicksort(a, x + 1, high);
}
}

main() {
int *a;
printf("Nhap bao nhieu so: ");
scanf("%d" , &n);
a = new int[n + 1];
nhap(a);
printf("Day so\n");
xuat(a);
printf("\nQuy trinh sap xep");
quicksort(a, 1, n);
printf("\nDay so da sap xep\n");
xuat(a);
}

# data[].attributes.attachment_link.readable_text
#include <stdio.h>
int n;
void nhap(int *a) {
	int i;
	for(int i = 1; i <= n; i++) {
		printf("So thu %2d: " ,i);
		scanf("%d", &a[i]);
	}
}

void xuat(int *a) {
	int i;
	for(i = 1; i <= n; i++)
		printf("%2d ", a[i]);
}

void hoanvi(int &x, int &y) {
	int tg;
	tg = x;
	x = y;
	y = tg;
}

int phandoan(int *a, int low, int high) {
	int chot, left, right;
	chot = a[high];
	left = low;
	right = high - 1;
	while(true) {
		while(left <= right && a[left] < chot)
			left++;
		while(left <= right && a[right] > chot)
			right--;
		if(left >= right)
			break;
		printf("\nChot= %2d     Left= %2d <-> Right= %2d : ", a[high], a[left], a[right]);
		hoanvi(a[left], a[right]);
		xuat(a);
		left++;
		right--;
	}
	printf("\nChot= %2d <-> Left= %2d               : ", a[high], a[left]);
	hoanvi(a[left], a[high]);
	xuat(a);
	return left;
}

void quicksort(int *a, int low, int high) {
	int x;
	if(low < high) {
		x = phandoan(a, low, high);
		quicksort(a, low, x - 1);
		quicksort(a, x + 1, high);
	}
}

main() {
	int *a;
	printf("Nhap bao nhieu so: ");
	scanf("%d" , &n);
	a = new int[n + 1];
	nhap(a);
	printf("Day so\n");
	xuat(a);
	printf("\nQuy trinh sap xep");
	quicksort(a, 1, n);
	printf("\nDay so da sap xep\n");
	xuat(a);
}
