mirror of https://github.com/TheAlgorithms/C
72 lines
1.2 KiB
C
72 lines
1.2 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
void swap(int *a, int *b)
|
|
{
|
|
int tmp = *a;
|
|
*a = *b;
|
|
*b = tmp;
|
|
}
|
|
|
|
int partition(int arr[], int low, int high)
|
|
{
|
|
int pivot = arr[low];
|
|
int i = low - 1, j = high + 1;
|
|
|
|
while (1)
|
|
{
|
|
/* Find leftmost element >= pivot */
|
|
do
|
|
{
|
|
i++;
|
|
} while (arr[i] < pivot);
|
|
|
|
/* Find rightmost element <= pivot */
|
|
do
|
|
{
|
|
j--;
|
|
} while (arr[j] > pivot);
|
|
|
|
/* if two pointers met */
|
|
if (i >= j)
|
|
return j;
|
|
|
|
swap(&arr[i], &arr[j]);
|
|
}
|
|
}
|
|
|
|
void partitionSort(int arr[], int low, int high)
|
|
{
|
|
if (low < high)
|
|
{
|
|
int value = partition(arr, low, high);
|
|
partitionSort(arr, low, value);
|
|
partitionSort(arr, value + 1, high);
|
|
}
|
|
}
|
|
|
|
void printArray(int arr[], int n)
|
|
{
|
|
int i;
|
|
for (i = 0; i < n; i++) printf("%d ", arr[i]);
|
|
printf("\n");
|
|
}
|
|
|
|
int main()
|
|
{
|
|
int arr[20];
|
|
int i, range = 100;
|
|
for (i = 0; i < 20; i++)
|
|
{
|
|
arr[i] = rand() % range + 1;
|
|
}
|
|
int size = sizeof arr / sizeof arr[0];
|
|
printf("Array: \n");
|
|
printArray(arr, size);
|
|
partitionSort(arr, 0, size - 1);
|
|
printf("Sorted Array: \n");
|
|
printArray(arr, size);
|
|
|
|
return 0;
|
|
}
|