LiveStreet

Быстрая сортировка (quicksort)

Быстрая сортировка является одним из самых быстрых алгоритмов сортировки массивов. Скорость работы примерно равна O(n log n) операций при сортировке n элементов.
Описание работы алгоритма:
— Из массива выбираем некоторый опорный элемент p;
— Делим массив на два подмассива, слева от p элементы меньшие либо равные p, а справа — большие либо равные p;
— Для каждого с подмассивов следует проделать ту же операцию, если в них более одного элемента.

Пошаговая работа сортировки:

5 2 7 1|9 3 8 11     // начальная последовательность
5 2 7 1|8 3 9 11
5 2 3 1|8 7 9 11
1 2|3 5|8 7|9 11
1 2|3 5|7 8|9 11     // результат

Реализация алгоритма:

#include <iostream>
#include <cstdlib>  // для Visual C++ заменить на <ctime>
using namespace std;

const int SIZE = 25;
int array[SIZE];

// заполнение массива случайными числами
void GenerationArray()
{
  // привязка ко времени для генерации чисел без повторений
  srand(time(0));

  for (int i=0; i<SIZE; i++)
  {
    // заполнение массива числами < 100
    array[i] = rand()%100;
  }
}

// вывод массива на экран
void ShowArray()
{
  for (int i=0; i<SIZE; i++)
  {
    cout << array[i] << " ";
  }

  cout << endl;
}

// High и Low - верхняя и нижняя границы подмассива, который надо отсортировать
void QuickSort(long int High, long int Low)
{
    long i, j;  // для хранения границ подмассива
    int p;      // для хранения опорного элемента
    int temp;

    i = Low;    // делаем копию нижней границы
    j = High;   // делаем копию верхней границы

    p = array[(Low+High)/2];    // выбираем опорный элемент

    // цикл будет работать, пока границы не пересекутся в массиве
    do
    {
        // если элемент нижней границы меньше опорного элемента,
        // передвигаем указатель i на один элемент вправо
        while (array[i] < p) i++;
        // если элемент верхней границы меньше опорного элемента,
        // передвигаем указатель j на один элемент влево
        while (array[j] > p) j--;

        // если границы не пересеклись по позициям в массиве,
        // меняем местами элементы i и j
        if (i <= j)
        {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;

            i++;
            j--;
        }
    } while (i <= j);

    // если в выделенном подмассиве [Low, j] больше одного элемента,
    // запускаем рекурсивно функцию QuickSort(long, long)
    if (j > Low) QuickSort(j, Low);

    // аналогично
    if (High > i) QuickSort(High, i);
}

int main()
{
    GenerationArray();

    ShowArray();

    QuickSort(SIZE-1, 0);

    ShowArray();

    return 0;
}

Сравнение скорости с сортировкой пузырьком и сортировкой выбором

В прошлой статье я сортировал 100 тысяч элементов сортировкой пузырьком (1 минута 38.731 секунд) и сортировкой выбором (28.313 секунд). Быстрая сортировка отсортировала столько же элементов за 0.024 секунды. Разница заметна :)
На сортировку 10 миллионов элементов ушло 2.333 секунды, в то время как на сортировку пузырьком 10 млн элементов ушло бы почти 23 месяца.