Алгоритм Быстр

Быстрая сортировка2

Эффективность

В отличие от рекурсивного алгоритма, верхним пределом для которого можно смело считать наборы длиной в 50 предметов, итеративный алгоритм способен обработать до 5 000 различных весов (общее количество предметов может быть гораздо больше).

Другие примеры сравнения рекурсивных и нерекурсивных алгоритмов, решающих одну и ту же задачу, будут приведены в лекции 12.

Возвратимся теперь к методам сортировки массивов, которым была посвящена лекция 4. Наиболее эффективный способ сортировки остался тогда не рассмотренным по причине того, что самая удобная его реализация подразумевает рекурсию.

1. Возьмем в сортируемом массиве срединный элемент: x:=a[(1+N)div 2];
2. Будем производить следующие действия:
1. начав с левого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[i], больший х;
2. начав с правого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[j], меньший х;
3. поменяем местами элементы a[i] и a[j];

до тех пор, пока не произойдет "рандеву". В результате массив будет разделен на две части. В левой части окажутся все компоненты, меньшие х, а в правой - большие х.

Теперь применим эти же действия к левой и к правой части массива - рекурсивно.

Дата добавления: 2014-01-03