В отличие от рекурсивного алгоритма, верхним пределом для которого можно смело считать наборы длиной в 50 предметов, итеративный алгоритм способен обработать до 5 000 различных весов (общее количество предметов может быть гораздо больше).
Другие примеры сравнения рекурсивных и нерекурсивных алгоритмов, решающих одну и ту же задачу, будут приведены в лекции 12.
Быстрая сортировка2
Возвратимся теперь к методам сортировки массивов, которым была посвящена лекция 4. Наиболее эффективный способ сортировки остался тогда не рассмотренным по причине того, что самая удобная его реализация подразумевает рекурсию.
Алгоритм Быстр
- Возьмем в сортируемом массиве срединный элемент: x:=a[(1+N)div 2];
- Будем производить следующие действия:
- начав с левого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[i], больший х;
- начав с правого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[j], меньший х;
- поменяем местами элементы a[i] и a[j];
до тех пор, пока не произойдет "рандеву". В результате массив будет разделен на две части. В левой части окажутся все компоненты, меньшие х, а в правой - большие х.
Теперь применим эти же действия к левой и к правой части массива - рекурсивно.
