Сортировка методом «челночка»
Как и сортировка методом «пузырька», челночная сортировка основана на перестановке двух соседних элементов в случае, если значение преды-дущего элемента больше, чем значение последующего (рассматриваем сор-тировку в неубывающем порядке). Но при челночной сортировке после та-кой перестановки происходит откат назад, к началу массива (при этом также, если выполнено условие сортировки, производится перестановка элементов).
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
Сортировка методом «Вставки»
Метод вставки основывается на нахождении минимального элемента и перестановки его на левую границу сдвигая все остальные элементы на одну позицию вправо.
T = [];
for n = [ 1000 : 1000 : 5000 ];
time = round( clock );
rand( 'seed', time(5)*time(6) );
m = rand( 1, n );
m = round( 1000*m );
t_start = clock;
for k=1:n-1
vm=m(k);
im=k;
for p=k+1:n
if m(p)<vm
im=p;
vm=m(p);
end
end
if im>k
m(k+1:im)=m(k:im-1);
m(k)=vm;
end
end
t_stop = clock;
t = t_stop( 6 ) - t_start( 6 );
T = [ T t ];
end;
plot( T ), grid on
Упражнение 2.
Сравнение быстродействия методов сортировки.
t = zeros(5);
figure, hold on, grid on, xlabel('N'), ylabel('y');
for N= 1000:1000:5000
m=fix(100*rand(1,N));
tstart=tic;
out=viborka_fun (m);
t(1,fix(N/1000))=toc(tstart);
end
for N= 1000:1000:5000
m=fix(100*rand(1,N));
tstart=tic;
out=vstavka_fun (m);
t(2,fix(N/1000))=toc(tstart);
end
for N= 1000:1000:5000
m=fix(100*rand(1,N));
tstart=tic;
out=Puzirjok_fun (m);
t(3,fix(N/1000))=toc(tstart);
end
for N= 1000:1000:5000
m=fix(100*rand(1,N));
tstart=tic;
out=chelnochok_fun (m);
t(4,fix(N/1000))=toc(tstart);
end
for N= 1000:1000:5000
m=fix(100*rand(1,N));
tstart=tic;
sort(m);
t(5,fix(N/1000))=toc(tstart);
end
for k=1:5
switch k
case 1 , col='r';
case 2 , col='m';
case 3 , col='b';
case 4 , col='g';
otherwise , col='c';
end
plot ( t(k,:), col);
end
axis equal;
legend ('Выборка','Всатвка','Пузырёк ','Челночёк ',' Сортировка')
Упражнение 3.
Разработать функцию, реализующую слияние двух уже отсортированных массивов в один.
function [rezult] = Objedinenije (m1 , m2)
n1=length(m1);
n2=length(m2);
rezult=zeros(1,n1+n2);
k1=1; k2=1; kr=1;
while (k1<=n1) && (k2<=n2)
if m1(k1)<=m2(k2)
k1=k1+1;
else
rezult (kr)=m2(k2);
k2=k2+1;
end
kr=kr+1;
end
k1=1; k2=1; kr=1;
while (k2<=n2) && (k1<=n1)
if m2(k2)<m1(k1)
k2=k2+1;
else
rezult (kr)=m1(k1);
k1=k1+1;
end
kr=kr+1;
end
if m2(n2) < m1(n1)
rezult (n1+n2)=m1(n1);
else
rezult (n1+n2)=m2(n2);
end
ФУНКЦИИ
function [x] = viborka_fun (x)
n=length(x);
for I = 1 : (n-1)
min_x = x( I ); index = I;
for J = (I+1) : n % перебираются все элементы от I+1 до n
if x( J ) < min_x
min_x = x( J ); % текущим минимальным
index = J; % фиксируется его номер
end
end
buff = x( I ); % текущий элемент и минимальный
x( I ) = x( index ); % меняются местами
x( index ) = buff;
end
end
function [x] = Puzirjok_fun (x)
n=length(x)
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;
end
function [x] = chelnochok_fun (x)
n=length(x)
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;
end
function [m] = vstavka_fun (m)
n=length(m);
for k=1:n-1
vm=m(k);
im=k;
for p=k+1:n
if m(p)<vm
im=p;
vm=m(p);
end
end
if im>k
m(k+1:im)=m(k:im-1);
m(k)=vm;
end
end
end
Метод Шелла.
При
сортировке Шелла сначала сравниваются
и сортируются между собой значения,
отстоящие один от другого на некотором
расстоянии
(о
выборе значения
см.
ниже).
После этого процедура повторяется для
некоторых меньших значений
,
а завершается сортировка Шелла
упорядочиванием элементов при
(то
есть обычной сортировкой
вставками).
Эффективность сортировки Шелла в
определённых случаях обеспечивается
тем, что элементы «быстрее» встают на
свои места (в простых методах сортировки,
например, пузырьковой,
каждая перестановка двух элементов
уменьшает количество инверсий
в списке максимум на 1, а при сортировке
Шелла это число может быть больше).
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
отсутствие потребности в памяти под стек;
отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.
n=length(x);
b=round(n/2);
while b >= 1
for I=1:n
if (I+b<=n) && (x(I) > x(I+b))
zam=x(I); x(I)=x(I+b); x(I+b)=zam;
end
end
I=0;
if round(b) > 1;
b=round(b/2);
else
b=b/2;
end
end
x
Вывод: Существует множество методов сортировки которые можно реализовать в системе MathLab. Судя по проведённому сравнению методов сортировке наиболее быстром оказался метод используемый во встроенной в систему функции sort, наиболее близким к нему оказалась сортировка выполненная по методу Шелла. Далее шли методы в таком порядке:
Метод выборки на месте.
Метода вставки.
Метод Челночка.
Метод пузырька.