Сортировка Хоара (1962 г.)

Это, по-видимому, наибо­лее популярный в мире метод внутрен­ней сортировки. Устано­вим указатели i и j на начало и конец таблицы. После сравнения клю­чей t_i, t_j изменяется один из индек­сов – i или j(увеличивается iили умень­шается j). Первым из­ме­няется j. Если t_i > t_j, ключи меняются местами, то пере­ключаемся на изменение проти­воположного указателя. Процесс продол­жается до тех пор, пока ука­за­тели не "встретятся". Пример выпол­не­ния

Рис. 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);

}

Оценим быстродействие алгоритма в наилучшем и наихудшем случае. В лучшем случае каждый отрезок разделяется точно по середине и всего разделений log₂N. В каждом отрезке проходятся все элементы, то есть для всех отрезков – N элементов. Таким образом, время оказывается пропорциональным N log₂N. В худшем случае массив ключей уже упорядочен. Каждое разделение создает два отрезка, в один из них входит 1 ключ, в другой – все остальные, следовательно, число разделений равно N и время сортировки пропорционально N². Ситуацию можно поправить выбором разделяющего ключа одним из двух способов:

- выбираем ключ со случайным номером на отрезке m…n

- выбираем медиану из трех ключей t_m, t_(m+n)/2, t_n.

Сортировка Хоара включена в библиотеки практически для всех компиляторов. Ниже приводится описание функции qsort, которая ее реализует.

void qsort(void *base, size_t nelem, size_t width,

int (*fcmp)(const void *, const void *));

Она имеет те же параметры, что и ранее описанная функция бинарного поиска (bsearch).