Сортировка Хоара (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++;

}

}