Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n lg n) обменов при упорядочении n элементов).

Использование функцию qsort из библиотеки stdlib.h

qsort( указатель_на_массив, количество_элементов, размер_элемента, функция_сравнения_элементов);

• функция_сравнения_элементов - является указателем на процедуру, поставляемую пользователем, которая сравнивает два элемента массива и возвращает значение, определяющее их отношение.

• Язык Си в примерах/Сортировка на основе qsort

Метод основан на разделении массива на части. Общая схема такова:

1. Из массива выбирается некоторый опорный элемент a[i].
2. Запускается функция разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], слева от него, а все ключи, большие, либо равные a[i] - справа, теперь массив состоит из двух частей, причем элементы левой меньше элементов правой.
3. Если в подмассивасивах более двух элементов, рекурсивно запускаем для них ту же функцию.
4. В конце получится полностью отсортированная последовательность.

Рассмотрим алгоритм более детально.

Делим массив пополам. Входные данные: массив a[0]…a[N] и элемент p, по которому будет производиться разделение.

1. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.
2. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p.
3. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] ⇐ p.
4. Далее, если i ⇐ j, меняем a[i] и a[j] местами и продолжаем двигать i,j по тем же правилам.
5. Повторяем шаг 3, пока i ⇐ j.

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

using namespace std;

template <class T>

void quickSortR(T a[], long N) {
// На входе - массив a[], a[N] - его последний элемент.

  long i = 0, j = N; 		// поставить указатели на исходные места
  T temp, p;

  p = a[ N>>1 ];		// центральный элемент

  // процедура разделения
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;

    if (i <= j){
      	temp = a[i];
	a[i] = a[j];
	a[j] = temp;
      	i++;
	j--;
    }

  }while ( i<=j );


  // рекурсивные вызовы, если есть, что сортировать 
  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}

void main(){
	srand(time(NULL));
	const long SIZE=10;
	int ar[SIZE];
	
	// до сортировки
	for(int i=0;i<SIZE;i++){
		ar[i]=rand()%100;
		cout<<ar[i]<<"\t";
	}
	cout<<"\n\n";
	quickSortR(ar,SIZE-1);

	// после сортировки
	for(int i=0;i<SIZE;i++){
		cout<<ar[i]<<"\t";
	}
	cout<<"\n\n";
}