Сортировка Хоара (1962 г.)
Это, по-видимому, наиболее популярный в мире метод внутренней сортировки. Установим указатели i и j на начало и конец таблицы. После сравнения ключей ti, tj изменяется один из индексов – i или j(увеличивается iили уменьшается j). Первым изменяется j. Если ti > tj, ключи меняются местами, то переключаемся на изменение противоположного указателя. Процесс продолжается до тех пор, пока указатели не "встретятся". Пример выполнения
Рис. 37 Сортировка Хоара
процесса изображен на рис.37. Заметим, что ключ 7 участвовал во всех сравнениях. Все ключи слева от него меньше его, все ключи справа – больше его, а сам ключ 7 занял свое окончательное положение. Рассмотренный процесс назовем разделением. Теперь можно применить тот же самый процесс к левой и правой части разделенной таблицы.
int Partition(int m, int n, int t[]){
// функция выполняет разделение участка массива ключей
// от m до n, возвращает точку расщепления
bool b=true; // если b==true, то перемещается правый указатель
// в противном случае - левый
while(m<n){
if(t[m]>t[n]){
swap(t[m],t[n]);
b=!b; // переключаемся на изменение другого указателя
}
if(b){
n--;
} else {
m++;
}
}
return m;
}
//---------------------------------------------------
void Hoar(int m, int n, int t[]){
// функция сортирует отрезок таблицы t на участке m…n
if(m>=n) return;
int k=Partition(m,n,t);
Hoar(m,k-1,t);
Hoar(k+1,n,t);
}
Оценим быстродействие алгоритма в наилучшем и наихудшем случае. В лучшем случае каждый отрезок разделяется точно по середине и всего разделений log2N. В каждом отрезке проходятся все элементы, то есть для всех отрезков – N элементов. Таким образом, время оказывается пропорциональным N log2N. В худшем случае массив ключей уже упорядочен. Каждое разделение создает два отрезка, в один из них входит 1 ключ, в другой – все остальные, следовательно, число разделений равно N и время сортировки пропорционально N2. Ситуацию можно поправить выбором разделяющего ключа одним из двух способов:
- выбираем ключ со случайным номером на отрезке m…n
- выбираем медиану из трех ключей tm, t(m+n)/2, tn.
Сортировка Хоара включена в библиотеки практически для всех компиляторов. Ниже приводится описание функции qsort, которая ее реализует.
void qsort(void *base, size_t nelem, size_t width,
int (*fcmp)(const void *, const void *));
Она имеет те же параметры, что и ранее описанная функция бинарного поиска (bsearch).