В своей книге "Исскуство программирования" Дональд Кнут описывает много алгоритмов сортировки. Процедуру по алгоритму Хоара относит к обменной сортировке с разделением. Этот алгоритм считается одним из самых быстрых для последовательной сортировки чисел. Разработал его англичанин Чарльз Хоар.
Суть алгоритма следующая. Допустим, имеется массив чисел:
3, 0, 1, 8, 7, 2, 5, 4, 9, 6
Сначала требуется выбрать базовое число. Обычно это первое число, тройка. Индекс этого числа 0. Сравниваем базовое число со вторым числом, имеющим наибольший индекс в массиве. Это шестерка. Левое число меньше чем правое, перестановку не делаем. Индекс второго числа уменьшаем на один. Теперь это число 9. Левое число меньше правого, перестановку не делаем. Индекс второго числа уменьшаем на единицу пока не доходим до числа два. индекс его 5. Левое число больше правого, делаем перестановку. Теперь 3 это элемент массива с индексом 5, 2 это элемент массива с индексом 0. Массив теперь выглядит так:
2, 0, 1, 8, 7, 3, 5, 4, 9, 6
Базовое число осталось 3, его индекс 5. Теперь проверку продолжаем слева на право, начиная с прежнего индекса базового числа плюс 1, это индекс 1. Сравниваем первое число 3 и второе 0. Левое число меньше правого, перестановку не делаем. Индекс второго числа увеличиваем на 1, это число 1 с индексом 2. Левое число меньше правого, перестановку не делаем. Индекс второго числа увеличиваем на 1, это число 8 с индексом 3. Левое число больше правого, меняем числа местами. Теперь базовое число 3 имеет индекс 3, число 8 имеет индекс 5. Массив стал выглядеть так:
2, 0, 1, 3, 7, 8, 5, 4, 9, 6
Теперь базовое число 3 с индексом 3 Сравниваем со вторым числом, имеющим индекс на единицу меньший прежнего индекса базового числа. Это число 7 с индексом 4. Левое число меньше правого и перестановку не делаем. Уменьшаем индекс второго числа на 1, получаем индекс 3. На этом месте находится базовое число. Завершаем первый цикл сортировки. Видим, что базовое число делит массив на две части. Любое число левой части меньше любого числа из правой. Продолжим рекурсивно проверку и перестановку чисел левой, а затем правой частей.
Дополнительно надо заметить что такое движение зигзагом по массиву увеличивает вероятность того, что массив будет поделен базовым числом на две приблизительно равные части. Это обеспечивает уменьшение сложности операции с О(n2) до O(n·log2 n)
Бесподобный ролик, визуализирующий процесс, имеется на Ютубе.
Ниже описание реализации. Функция hoarsort имеет аргументы begin и end, которые обозначают индексы первого и второго чисел. Индексы двигаются друг другу навстречу. Когда индексы совпадают, выполнение функции завершается. Сначала находится индекс базового числа выполнением функции partitition. Базовое число делит кусок массива на две части. С каждой из частей рекурсивно выполняется функция hoarsort.
function sortAlgorithm(){
let mainArr: number[] = [];
let btn1 = document.getElementById("btn1");
let btn2 = document.getElementById("btn2");
btn1.addEventListener("click", (e:Event) => handleClickBtn1()); //получаем массив для сортировки
btn2.addEventListener("click", (e:Event) => handleClickBtn2()); //сортируем массив
function handleClickBtn1(): any {
let nextNum: number = Number((document.getElementById("input1") as HTMLInputElement).value); //следующее число
mainArr.push(nextNum);
console.log(mainArr);
(document.getElementById("text1") as HTMLInputElement).value = String(mainArr);
}
function handleClickBtn2(): any {
console.log(mainArr);
let begin: number = 0;
let end: number = mainArr.length - 1;
let directionForward: boolean = true;
hoarsort(begin, end);
console.log(mainArr);
(document.getElementById("text2") as HTMLInputElement).value = String(mainArr);
function partitition(begin: number, end:number): number{
while(begin < end){
if(mainArr[begin] > mainArr[end]) {
let temp: number = mainArr[begin]; //swap
mainArr[begin] = mainArr[end];
mainArr[end] = temp;
directionForward = !directionForward;
}
if(directionForward){
end--;
} else {
begin++;
}
}
return begin;
}
function hoarsort(begin: number, end:number): void {
if(begin >= end){
return;
}
let base: number = partitition(begin, end);
hoarsort(begin, base - 1);
hoarsort(base + 1, end);
}
}
}
Добавить число:
Исходный массив чисел:
Отсортированный массив: