Алгоритмы сортировки обменом основаны на перестановке двух соседних элементов. Соседние элементы меняются местами, если элемент с меньшим номером имеет большее значение (напомним, что речь идет о сортировке в неубывающем порядке).
Сортировка методом «пузырька»
Метод «пузырька» назван так по сходству процессов при сортировке и подъема воздушного пузырька в стакане с жидкостью. Допустим, что жидкость состоит из отдельных слоев. Тогда образовавшийся на дне воздушный пузырек поднимается вверх, последовательно меняясь местами с расположенными над ним слоями воды.
Также и при сортировке массива, если максимальный элемент находится на левой границе, то вследствие перестановок он за один прогон будет «выдавлен» на правую границу. Очевидно, что после первого этапа упорядочения массива, значение максимального элемента переместится на правую границу. Следовательно, второй этап упорядочения должен производиться уже не до правой границы, а до элемента, смещенного влево относительно правой границы на один. И так далее. Очевидно также, что если массив уже упорядочен, то нет необходимости реализовывать алгоритм до конца. В связи с этим, метод пузырька предполагает возможность подсчета количества перестановок элементов (хотя это и не обязательно). Процесс сортировки заканчивается, если осуществлен полный перебор элементов массива или количество перестановок равно 0. Иллюстрацией к сортировке методом «пузырька» может служить следующая схема. На ней представлен массив из четырех чисел. Два сравниваемых значения взяты в квадратные скобки. Если в результате сравнения элементы меняются местами, то они выделены жирным шрифтом. В результате первого перебора массива произошло три (L=3) перестановки, в результате которых значение 48 переместилось в крайний правый элемент.
После того, как первый перебор закончен, граница смещается на единицу (перенос пунктирной линии на схеме). В результате второго перебора произошла еще одна перестановка (L=4). Как видно, массив уже упорядочен. Поэтому последний перебор (а это сравнение текущих значений первого и второго элементов) не вносит в него изменений.
| Исходный массив | ||||
| 1) | [48] | [21] | ||
| 2) | [48] | [6] | ||
| 3) | [48] | [39] | ||
| После первого перебора | ||||
| L=3 | ||||
| 4) | [21] | [6] | ||
| 5) | [21] | [39] | ||
| После второго перебора | ||||
| L=4 | ||||
| 6) | ||||
| Окончательное состояние |
Сортировка методом «пузырька» может быть проиллюстрирована следующей программой (в данном примере нет подсчета числа перестановок):
% программная реализация сортировки массива методом
% "пузырька" (сортировка обменом)
clear all;
T = [];
for n = [ 1000: 1000: 5000 ];
time = round(clock);
rand('seed', time(5)*time(6));
x = rand(1, n);
x = round(100*x);
t_start = clock;
J = n - 1; % устанавливается начальное значение
% правой "границы" сортировки
while J ~= 0 % пока эта граница не совпала с началом массива
for I = 1: J % перебираются все элементы с 1-го
% до "границы" сортировки
if x(I) > x(I+1) % если условие упорядочения массива
% не выполнено, то два соседних
buff = x(I); % меняются местами
x(I) = x(I+1);
x(I+1) = buff;
end;
end;
J = J - 1; % "граница" сортировки сдвигается влево
end;
t_stop = clock;
t = t_stop(6) - t_start(6);
T = [ T t ];
end;
plot(T), grid on
Как и в предыдущем случае строится график зависимости времени сортировки от объема сортируемого массива.
Челночная сортировка
Как и сортировка методом «пузырька», челночная сортировка основана на перестановке двух соседних элементов в случае, если значение предыдущего элемента больше, чем значение последующего (рассматриваем сортировку в неубывающем порядке). Но при челночной сортировке после такой перестановки происходит откат назад, к началу массива (при этом также, если выполнено условие сортировки, производится перестановка элементов).
Как и в случае сортировки методом «пузырька», челночная сортировка может быть проиллюстрирована следующей схемой (обозначения такие же, как и в предыдущем случае). Как видно из схемы, после второго шага (после сравнения и перестановки чисел 48 и 6) происходит откат до начала массива (в данном случае сравнение чисел 21 и 6). Далее процесс возобновляется с того места, откуда был произведен откат. Очевидно, что челночная сортировка более эффективна, чем сортировка методом «пузырька». Считается, что из рассмотренных алгоритмов челночная сортировка наиболее выгодна, особенно для больших массивов, элементы которых являются в свою очередь сложными структурами (структурами или ячейками). Однако более точно ответить на этот вопрос можно, только проведя сравнение рассмотренных методов сортировки.
| Исходный массив | ||||
| 1) | [48] | [21] | ||
| 2) | [48] | [6] | ||
| откат | [21] | [6] | ||
| 4) | [48] | [39] | ||
| откат | [21] | [39] | ||
| Окончательное состояние |
Челночная сортировка (как и ранее - по возрастанию) может быть проиллюстрирована следующим фрагментом:
% программная реализация сортировки массива методом
% челночной сортировки (сортировка обменом)
clear all;
T = [];
for n = [ 1000: 1000: 5000 ];
time = round(clock);
rand('seed', time(5)*time(6));
x = rand(1, n);
x = round(100*x);
t_start = clock;
for I = 1: (n-1); % перебираются все элементы от первого
% до предпоследнего
if x(I) > x(I+1) % если условие упорядочения массива
% не выполнено
for J = I: -1: 1 % откат назад от текущего элемента до первого
if x(J) > x(J+1) % и при необходимости перестановка
buff = x(J);
x(J) = x(J+1);
x(J+1) = buff;
end;
end;
end;
end;
t_stop = clock;
t = t_stop(6) - t_start(6);
T = [ T t ];
end;
plot(T), grid on
В заключение отметим, что целью практического занятия является ознакомление с методами сортировки массивов, сравнение эффективности различных методов и зависимости времени сортировки от объема массива. Кроме того, необходимо сравнить указанные методы с функцией Matlab sort, которая собственно и предназначена для проведения сортировки массивов данных. Сортировке функцией sort необходимо подвергать тот же массив, что сортируется и другими методами. Для этого значения сформированного массива х можно передать другому массиву (например, y). И уже этот массив подвергнуть сортировке стандартной функцией Matlab. Очевидно, что при этом необходимо также фиксировать и время этой сортировки.
Все разрабатываемые программы должны обеспечивать визуализацию результатов, вывод их в рабочую область. В отчете должны быть представлены графики (допускаются построенные «от руки») зависимостей времени сортировки от объема массива. В заключение работы должен быть сделан обоснованный вывод о наиболее эффективном методе сортировки.