Доброго всем времени суток!!!
Суть (если коротко) данного вида сортировки заключается в определении места опорного элемента (нулевой элемент в массиве) и постановки его на место (т. е. его надо поставить на место, которое он бы занял в отсортированном массиве). Попутно происходит частичная сортировка массива. Рассмотрим первую стадию сортировки:
ИМЕЕМ МАССИВ
0. 12, 0, 25, 1, 36, 11, 7, 19, 23, 21
С правой стороны начинаем перебирать элементы, ищем элемент < 12. 7 < 12. Меняем их местами. Получим:
1. 7, 0, 25, 1, 36, 11, 12, 19, 23, 21
С левой стороны начинаем перебирать элемены, ищем элемент > 12. 25 > 12. Меняем их местами. Получим:
2. 7, 0, 12, 1, 36, 11, 25, 19, 23, 21
С правой стороны начинаем перебирать элементы, ищем элемент < 12. 11 < 12. Меняем их местами. Получим:
3. 7, 0, 11, 1, 36, 12, 25, 19, 23, 21
С левой стороны начинаем перебирать элемены, ищем элемент > 12. 36 > 12. Меняем их местами. Получим:
4. 7, 0, 11, 1, 12, 36, 25, 19, 23, 21
В результате получаем массив, где все элементы слева от опорного не превышают опорный элемент и все элементы справа от опорного не менее опорного.
Первая стадия закончена. Далее запускаем рекурсию. Левый и правый подмассивы должны произвести прогон и разбить два подмассива еще на два подмассива. И так далее.
Сортировка действительно быстрая. 1000 000 элементов массива данным методом сортируются быстрее, чем 10 000 пузырьковым методом (секундомером не мерял, все строго по ощущениям).
#include <stdlib.h>
#include <time.h>
#define SIZE 1000000
void determination(int wArray[]); //функция присвоения значений массиву
void printing(int wArray[]); //функция вывода массива на экран
int quickSort(int wArray[], int, int); //функция поиска номера члена массива (и постановка их на свое место)
void swap (int *element1Ptr, int *element2Ptr);
int main()
{
int Array[SIZE] = {0};//{12, 0, 25, 1, 36, 11, 7, 19, 23, 31};
printf("\n");
srand (time(NULL));
determination(Array);
printing(Array);
printf("\n\n");
quickSort(Array, 0, (SIZE - 1));
printing(Array);
}
void determination(int wArray[])//функция присвоения значений массиву
{
for (int i = 0; i < SIZE; i++)
{
wArray[i] = rand() % (3 * SIZE);
}
}
///////////////////////////////////////////////////////////
//ОДИН ПРОХОД РАБОТАЕТ ///////////
//ТРЕБУЕТСЯ РЕАЛИЗОВАТЬ РЕКУРСИЮ
//РЕКУРСИ РАБОТАЕТ
void printing(int wArray[])//функция вывода массива на экран
{
for (int i = 0; i < SIZE; i++)
{
printf("%d\t%d\n", i, wArray[i]);
}
printf("\n\n");
}
int quickSort(int wArray[], int left, int right)
{
int allowEntry = wArray[left]; //устанавливаем разрешающий элемент(0-й элемент массива)
int allowEntryPtr = left;
int l_hold = left, r_hold = right;
while (left < right)
{
while((allowEntry <= wArray[right]) && (left < right)) //ищем элементы меньшие разрешающего начиная справа
{
right--;
}
if (left != right) //и меняем их местами с разрешающим элементом
{
swap (&wArray[allowEntryPtr], &wArray[right]);
allowEntryPtr = right;
left++;
//printing(wArray);
}
while ((allowEntry >= wArray[left])&& (left < right)) //ищем элементы большие разрешающего начиная слева
{
left++;
}
if (left != right) //и меняем их местами с разрешающим элементом
{
swap (&wArray[allowEntryPtr], &wArray[left]);
allowEntryPtr = left;
right--;
//printing(wArray);
}
}
allowEntryPtr = left;
left = l_hold;
right = r_hold;
if (left < allowEntryPtr)
{
quickSort(wArray, left, allowEntryPtr - 1);
}
if (right > allowEntryPtr)
{
quickSort(wArray, allowEntryPtr + 1, right);
}
}
void swap (int *element1Ptr, int *element2Ptr) //ФУНКЦИОНИРУЕТ
{
int temp;
temp = *element1Ptr;
*element1Ptr = *element2Ptr;
*element2Ptr = temp;
}