Быстрая сортировка.
"Быстрая сортировка" - была разработана около 40 лет назад и является
наиболее широко применяемым и в принципе самым эффективным алгоритмом. Метод
основан на разделении массива на части. Общая схема такова:
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/2 ]; // центральный элемент
// процедура разделения
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";
}
|
Алгоритм рекурсии.
1. Выбрать опорный элемент p - середину массива
2. Разделить массив по этому элементу
3. Если подмассив слева от p содержит более одного элемента, вызвать
quickSortR для него.
4. Если подмассив справа от p содержит более одного элемента, вызвать
quickSortR для него.
