Сортировка пузурьковым методом.
Наиболее известной (и наиболее "бесславной") является сорти- ровка пузырьковым методом. Ее популярность объясняется запоминаю- щимся названием и простотой алгоритма. Однако, эта сортировка яв- ляется одной из самых худших среди всех когда-либо придуманных сортировок. Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название про- исходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Ни- же показана самая простая форма программы сортировки методом пу- зырька: { сортировка пузырьковым методом} procedure Bubble(var item: DataArray; count:integer); var i,j: integer; x: DataItem; begin for i := 2 to count do begin for j := count downto i do if item[j-1]>item[j] then begin x := item[j-1]; item[j-1] := item[j]; item[j] := x; end; end; end; {конец сортировки пузырьковым методом} В этом случае данное "item" является массивом элементов "DataItem", который сортируется, а данное "count" содержит число элементов в массиве. Сортировка пузырьковым методом имеет два цикла. Поскольку число элементов массива задается переменной "count", внешний цикл вызывает просмотр массива count - 1 раз. Это обеспечивает нахож- дение каждого элемента в своей позиций после завершения процеду- ры. Внутренний цикл предназначен для фактического выполнения опе- раций сравнения и обмена. Эта версия сортировки пузырьковым методом может сортировать символьный массив в порядке возрастания значений элементов. Нап- ример, следующая короткая программа сортирует строку, которая считывается с дискового файла "test.dat". Эта же программа может использоваться с другими подпрограммами сортировки, которые при- водятся в этой главе. program SortDriver; {эта программа будет считывать 80 или меньше символов с дискового файла "test.dat", отсортирует их и выдаст pезультат на экран дисплея } type DataItem = char; DataArray = array [1..80] of char; var test: DataArray; t, t2: integer; testfile: file of char; { сортировка пузырьковым методом} procedure Bubble(var item: DataArray; count:integer);
var i,j: integer; x: DataItem; begin for i := 2 to count do begin for j := count downto i do if item[j-1]>item[j] then begin x := item[j-1]; item[j-1] := item[j]; item[j] := x; end; end; end; begin Assign(testfile, 'test.dat'); Reset(testfile); t := 1; { считывание символов,которые будут сортироваться.} while not Eof(testfile) do begin read(testfile, test[t]); t := t+1; end; t := t-2; {скорректировать число считанных элементов } Bubble(test, t); { сортировать массив } { выдать отсортированный массив символов } for t2 := 1 to t do write(test[t2]); WriteLn; end. Для иллюстрации работы сортировки пузырьковым методом ниже даны результаты каждого этапа сортировки массива "dcab": - исходное положение: d c a b; - первый проход: a d c b; - второй проход: a b d c; - третий проход: a b c d. При анализе всякой сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худших случа- ях. Для сортировки пузырьковым методом число сравнений остается
неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это оз- начает, что при сортировке пузырьковым методом всегда выполняется 1/ 2 (n**2-n) операций сравнения, где "n" задает число сортируе- мых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Их перемножение даст указанную формулу. Число операций обмена будет нулевым для наилучшего случая, когда исходный массив уже является отсортированным. Число опера- ций обмена для среднего случая будет равно 3/4 (n**2-n), а для наихудшего случая будет равно 3/2 (n**2-n) раз. Вывод этих формул выходит за пределы этой книги. Можно заметить, что по мере ухуд- шения упорядоченности исходного массива число неупорядоченных элементов приближается к числу сравнений (каждый неупорядоченный элемент требует три операции обмена). Сортировку пузырьковым ме- тодом называют квадратичным алгоритмом, поскольку время его вы- полнения пропорционально квадрату числа сортируемых элементов. Сортировка большого числа элементов пузырьковым методом потребует очень много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива. Например, если не учитывать время операций обмена, выполняе- мых для перестановки неупорядоченных элементов, то тогда при вы- полнении одной операции сравнения в течение 0,001 секунд сорти- ровка десяти элементов займет 0,05 секунд, сортировка ста элементов займет пять секунд, а сортировка 1000 элементов займет 500 секунд. Сортировка 100 000 элементов (такой размер имеет не- большой телефонный справочник) потребовала бы 5000000 секунд или около 1400 часов (т.е. два месяца непрерывной работы)! Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристи- ки. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направ- лении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Ниже показана улучшенная версия сортировки пузырьковым ме- тодом, получившая название "челночной сортировки" из-за соот- ветствующего характера движений по массиву. Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выпол- нения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на нез- начительную величину.
| 
