Программирование на C и C++

Онлайн справочник программиста на C и C++

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

Аватар пользователя 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;
        }