Реализация Быстрой сортировки

Аватар пользователя merkul40
пт, 02/16/2018 - 01:14 -- merkul40

Доброго всем времени суток!!!
Суть (если коротко) данного вида сортировки заключается в определении места опорного элемента (нулевой элемент в массиве) и постановки его на место (т. е. его надо поставить на место, которое он бы занял в отсортированном массиве). Попутно происходит частичная сортировка массива. Рассмотрим первую стадию сортировки:

ИМЕЕМ МАССИВ

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 <stdio.h>
#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;
	}