Метод пузырька.

( метод назван также обменной сортировкой с выбором) .

Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в там случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю оперно для оставшихся неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.

Сортировка выбором

На этот раз при просмотре мaccива мы будем искать наименьший элемент, Сравнивая его с первым. Если такой элемент найден, поменяем его местами с первым. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать подобным образом, пока не рассортируем весь массив.

Метод Шелла

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

Метод Хoopа

Этот метод, называемый также быстрой сортировкой(QuickSort), был Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).

Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами.

3.1 Разветвляющиеся алгоритмы

Задачи этой темы посвящены использованию условных операторов; следует в решениях обойтись без циклов и массивов. Применение операторов ветвления позволяет использовать простейшую защиту программы от сбоев: контроль входных данных и промежуточных результатов.

Пример. Факультету выделен стипендиальный фонд в раз­мере/р./мес. Результаты сессии таковы: п₁ -«отличников», п₂ «хорошистов», и₃ «троечников». Повышенная стипендия (для отличников) составляет s_t p., обычная — s₂ p.; задолжни­ки стипендии лишаются. Сколько студентов каждой катего­рии могут получать стипендию и каков будет остаток фонда на материальную'помощь малоимущим?

Решение можно записать в виде следующей Паскаль-про­граммы:

Program Stipen (Input. Output);

var nl. n2. n3. kl. k2. k3, s. si. s2.

fond: Integer; begin

Write ('Каков размер фонда? '):

ReadLn (fond);

Write ('Сколько в категориях '."отл."."хор.''.^нудовл.^н? ');

ReadLn (nl. n2. пЗ);

Write ('Размер повышенной и нормальной ',стипендий: ');

ReadLn (si. s2): if fond > sl*nl then kl :- nl else kl :- fond div si: fond := fond - sl*kl: {остаток для остальных категорий} if fond > s2*n2 then k2 := n2

else k2 := fond div s2: fond :- fond - s2*k2;

{остаток для троечников} if fond > s2*n3 then k3 :- n3

else k3 :■» fond div s2;

fond :- fond - s2*k3; {остаток - резерв}

WriteLn ('Выдавать стипендию:');

WriteLn (kl." отличникам:');

if k2 > 0 then

WriteLn (k2." хорошистам;');

if k3 > 0 then

WriteLn (k3.' троечникам:');

WriteLn ('Резерв фонда составит '. fond,' рублей');

end.