Быстрая сортировка

Быстрая сортировка - это один из наиболее эффективных алгоритмов сортировки. При быстой сортировке используется следующая стратегия:

1. Массив разбивается на меньшие подмассивы
2. Подмассивы сортируются
3. Отсортированные подмассивы объединяются

Быструю сортировку можно реализовать несколькими способами, но цель каждого подхода будет заключаться в выборе элемента данных и помещении его в правильную позицию (этот элемент будет называться точкой разбиения), таким образом, чтобы все элементы слева от точки разбиения оказались меньше (или предшествовали) точки разбиения, а все элементы справа от точки разбиения оказались больше (или следовали за) точки разбиения. Способ выбора точки разбиения оказывает огромное влияние на производительность сортировки. Рассмотрим рекурсивную реализацию быстрой сортировки.

Алгоритм:

1. Выбрать элемент данных и сделать его точкой разбиения таким образом, чтобы он разбивал массив на левый и правый подмассивы, как было описано выше.
2. Применить быструю сортировку к левому подмассиву.
3. Применить быструю сортировку к правому подмассиву.

Пример алгоритма нахождения точки разбиения:

1. Выбрать первый элемент данных как точку разбиения. Point = A[first].
2. Инициализировать два указателя поиска, i и j, чтобы i = first (наименьший индекс подмассива), а j = last (наибольший индекс подмассива).
3. Используя указатель поиска i, найти, начиная слева, элемент данных, который будет больше или равен точке разбиения (Point).
4. Используя указатель поиска j, найти, начиная справа, элемент данных, который будет меньше или равен точке разбиения (Point).
5. Если i < j, то поменять местами A[i] и A[j].
6. Повторить пункты 2 - 4, пока не выполнится условие i > j.
7. Поменять местами точку разбиения и A[j]. 

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

// Быстрая сортировка

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <time.h>

template <typename T>
void QSort(T array[] /* Сортируемый массив */, 
 int first /* Начальный индекс */, int last /* Конечный индекс */)
{
 if(first < last)
 {
 // Переменная для просмотра массива слева
 int i; 
 // Переменная для просмотра массива справа
 int j; 
 // Временная переменная для обмена значений элементов
 T temp; 
 // Элемент - точка разбиения массива
 T point; 

 // Принимаем за точку разбиения первый элемент массива
 // (можно выбрать любой)
 point = array[first];

 i = first;
 j = last;

 while(i < j)
 {
 // Ищем слева элемент, который >= точки разбиения
 while(array[i] <= point && i < last)
 i++;
 // Ищем справа элемент, который <= точки разбиения
 while(array[j] >= point && j > first)
 j--;

 if(i < j)
 {
 temp = array[i];
 array[i] = array[j];
 array[j] = temp;
 }
 }

 // Помещаем точку разбиения в правильную позицию,
 // т. е. все элементы слева не больше нее, а 
 // все элементы справа не меньше нее

 /* Примечание !!! */
 // Использовать переменную point нельзя, так как она всего
 // лишь копия элемента массива, являющегося точкой разбиения
 /*****************/

 temp = array[first];
 array[first] = array[j];
 array[j] = temp;

 // Сортируем левый и правый подмассивы
 QSort(array, first, j - 1);
 QSort(array, j + 1, last);
 }
}

// Функция для вывода массива
template <typename T>
void PrintArray(T array[], int size)
{
 // функция setw(n) создает поле для вывода с шириной n символов
 for(int i = 0; i < size; i++)
 {
 if(i % 5 == 0)
 cout << endl;
 cout << setw(15) << array[i];
 }
 cout << endl;
}

// Тестирование
void main()
{
 // Инициализация генератора случайных чисел
 srand(time(0));
 // Размер массивов
 const N = 10;
 
 int i;
 int a[N];
 float b[N];

 // Инициализация массивов случайными числами в диапазоне от -10 до 10
 for(i = 0; i < N; i++)
 {
 a[i] = rand() % 21 - 10;
 b[i] = rand() / (float)32767 * 20 - 10;
 }

 // Вывод массивов
 cout << "Array A:\n";
 PrintArray(a, N); 

 cout << "Array B:\n";
 PrintArray(b, N); 

 // Сортировка массивов
 QSort(a, 0, N - 1);
 QSort(b, 0, N - 1);

 // Вывод отсортированных массивов
 cout << endl;
 cout << "Array A:\n";
 PrintArray(a, N); 

 cout << "Array B:\n";
 PrintArray(b, N); 
}