/ * Быстрая сортировка после устранения хвостового вызова * /
#include<stdio.h>
Утилита для замены двух элементов
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/ * Эта функция принимает последний элемент в качестве точки поворота, помещает элемент точки поворота в правильное положение в отсортированном массиве и размещает все меньшие (меньше, чем точки поворота) слева от точки поворота и все большие элементы справа от точки поворота. Он использует алгоритм разбиения Lomuto. * /
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; `// pivot`
int i = (low - 1); `// Index of smaller element`
for (int j = low; j <= high- 1; j++)
{
`// If the current element is smaller than or equal to pivot `
if (arr[j] <= pivot)
{
i++; `// increment index of smaller element`
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/ * Основная функция, реализующая QuickSort arr [] -> Массив для сортировки, низкий -> Начальный индекс, высокий -> Конечный индекс * /
void quickSort(int arr[], int low, int high)
{
while (low < high)
{
`/* pi is partitioning index, arr[p] is now at right place */`
int pi = partition(arr, low, high);
`// Separately sort elements before partition and after partition`
quickSort(arr, low, pi - 1);
low = pi+1;
}
}
Функция для печати массива
void printArray(int arr[], int size)
{
for (int i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
Программа драйвера для проверки вышеуказанных функций
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}