Quá trình quickSort là phân vùng (). Mục tiêu của phân vùng là đưa ra một mảng và một phần tử của mảng
làm trục, đặt x ở vị trí chính xác và đặt tất cả các phần tử nhỏ hơn x vào trước x,
đặt tất cả các phần tử lớn hơn x vào sau x. Tất cả quy trình được thực hiện lặp đi lặp lại.
/* C thực hiện QuickSort */
#include<stdio.h>
// Hàm để hoán đổi 2 phần tử
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/* Hàm này nhận phần tử cuối cùng làm pivot,
đặt phần tử pivot vào đúng vị trí của nó trong mảng đã sắp xếp
và đặt tất cả các phần tử nhỏ hơn (nhỏ hơn pivot) ở bên trái của pivot
và tất cả các phần tử lớn hơn ở bên phải của pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // chỉ số của phân tử nhỏ hơn
for (int j = low; j <= high- 1; j++)
{
// Nếu phân tử hiện tại nhỏ hơn pivot
if (arr[j] < pivot)
{
i++; // tăng chỉ số của phân tử nhỏ hơn
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* Thực hiện quickSort
arr[] --> mang can sap xep,
low --> chỉ số bắt đầu,
high --> chỉ số kết thúc */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi là chỉ số đang phân vùng, arr[p] bây giờ ở đúng vị trí */
int pi = partition(arr, low, high);
// Sắp xếp riêng biệt các phần tử trước
// phân vùng và sau phân vùng
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Hiện thị 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 n;
printf("Enter n: ");scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++){
printf("a[%d] = ",i+1);scanf("%d",&arr[i]);
}
quickSort(arr, 0, n-1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
