Тема: Швидке сортування, запропоноване Хоаром в 1962р.
Вітаю всіх!
Намагаюсь зрозуміти принцип швидкого сортування, запропонованого Хоаром в 1962р., проте це виявилось не таким легким завданням. Є зображення і стаття в вікі, які пояснюють суть методу, проте важко зрозуміти все одно.
КіР приводять такий код на пояснення цього методу:
void qsort(int v[], int left, int right){
int i, last;
if(left>=right)
return;
swap(v, left, (left+right)/2);
last = left;
for(i = left+1; i<=right; i++)
if(v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last);
qsort(v, left, last-1);
qsort(v, last+1, right);
}
void swap(int v[], int i, int j){
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}Я спробував вирішити по ньому приклад на аркуші паперу, масив магічним способом відсортувався, але самого алгоритму я не зрозумів.
В гуглі є вдосталь англомовного матеріалу, але можливо хтось уже мав справу із такою задачею і зможе мені тут розказати що і до чого, бо на даний момент мені потрібно знати суто як працює цей алгоритм, а конкретно цей приклад.
