Сортировка методом «пузырька»

1 2 3 4 5

М.А.И.

(Национальный Исследовательский Университет)

Лабораторная работа № 10

Практикум № (Сортировка)

МЕТОДЫ СОРТИРОВКИ

Вариант № 24

Оформил: Абрамов Иван Андреевич

Проверил: Кривилёв А. В.

Москва 2012

Цель работы: ознакомление с методами сортировки массивов, сравнение эффективности различных методов и зависимости времени сортировки от объема массива.

Упражнение 1.

Сортировка выборкой на месте

Алгоритм сортировки массива выборкой на месте состоит в следующем. Производится последовательный перебор элементов массива начиная с пер-вого. Для взятого текущего элемента в оставшейся части массива (от те-кущего элемента и до крайней правой границы) находится минимальное значение. Далее текущий элемент и элемент, имеющий минимальное значе-ние, переставляются местами. Очевидно, данный метод сортировки предпо-лагает выполнение двух операторов цикла: 1) перебор элементов от пер-вого и до последнего; 2) перебор элементов от текущего и до правой границы.

Процесс сортировки можно проиллюстрировать графически следующим об-разом (стрелками показаны элементы, которые меняются местами): x1	x2	…	…	…	xmin	…	…
xmin	x2	…	…	xmin’	…	…	…
xmin	xmin’	x3	…	…	…	xmin”…	…
…
xmin	xmin’	xmin”	x4	…	…	…	…

T = []; % формируется пустой массив времени сортировки

N = [];

for n = [ 1000: 1000: 5000 ]; % меняется размерность массива данных

N = [ N n ];

time = round(clock); % определяется текущее время для инициализации датчика случайных чисел

rand('seed', time(5)*time(6)); % осуществляется инициализация датчика случайных чисел

x = rand(1, n); % генерируется массив случайных чисел из диапазона [ 0 1 ]

x = round(100*x); % случайный массив целых двузначных чисел

t_start = clock; % фиксируется время старта сортировки

for I = 1: (n-1)

min_x = x(I); index = I; % предполагается, что минимальный элемент имеет номер I

for J = (I+1): n % перебираются все элементы от I+1 до n

if x(J) < min_x % если находится элемент меньше, чем

текущий минимум, то он становится

min_x = x(J); % текущим минимальным

index = J; % фиксируется его номер

end

buff = x(I); % текущий элемент и минимальный

x(I) = x(index); % меняются местами

x(index) = buff;

end

t_stop = clock; % фиксируется время остановки сортировки

t = t_stop(6) - t_start(6); % вычисляется время сортировки (сек)

T = [ T t ]; % формируется массив времен сортировки

end;

plot(N, T), grid on % строится график зависимости времени

Сортировка методом «пузырька»

Алгоритмы сортировки обменом основаны на перестановке двух соседних элементов. Соседние элементы меняются местами, если элемент с меньшим номером имеет большее значение (напомним, что речь идет о сортировке в неубывающем порядке). Если максимальный элемент находится на левой границе, то вследствие перестановок он за один прогон будет «выдавлен» на правую границу. Очевидно, что после первого этапа упоря-дочения массива, значение максимального элемента переместится на пра-вую границу. Следовательно, второй этап упорядочения должен произво-диться уже не до правой границы, а до элемента, смещенного влево отно-сительно правой границы на один. И так далее.

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-го

% до "границы" сортировки