Алгоритм сортировки прямым выбором в некотором смысле противоположен сортировке прямыми включениями.
При прямом включении на каждом шаге рассматривается только один очередной элемент входной последовательности и все элементы готовой последовательности для нахождения места включения.
При прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы входной последовательности и найденный элемент помещается как очередной элемент в конец готовой последовательности.
Метод сортировки прямым выбором основан на следующих правилах:
· Выбирается элемент с наименьшим ключом.
· Он меняется местами с первым элементом a0.
· Затем эти операции повторяются с оставшимися n-1 элементами, n-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.
Таблица 1
| 0,57 | -0,11 | 0,27 | 0,48 | 0,05 | -24 | 0,09 | 1,46 | -0,39 | -1,00 | ||
| -24 | -0,11 | 0,27 | 0,48 | 0,05 | 0,57 | 0,09 | 1,46 | -0,39 | -1,00 | ||
| -24 | -1,00 | 0,27 | 0,48 | 0,05 | 0,57 | 0,09 | 1,46 | -0,39 | -0,11 | ||
| -24 | -1,00 | -0,39 | 0,48 | 0,05 | 0,57 | 0,09 | 1,46 | 0,27 | -0,11 | ||
| -24 | -1,00 | -0,39 | -0,11 | 0,05 | 0,57 | 0,09 | 1,46 | 0,27 | 0,48 | ||
| -24 | -1,00 | -0,39 | -0,11 | 0,05 | 0,57 | 0,09 | 1,46 | 0,27 | 0,48 | ||
| -24 | -1,00 | -0,39 | -0,11 | 0,05 | 0,09 | 0,57 | 1,46 | 0,27 | 0,48 | ||
| -24 | -1,00 | -0,39 | -0,11 | 0,05 | 0,09 | 0,27 | 1,46 | 0,57 | 0,48 | ||
| -24 | -1,00 | -0,39 | -0,11 | 0,05 | 0,09 | 0,27 | 0,48 | 0,57 | 1,46 | ||
| -24 | -1,00 | -0,39 | -0,11 | 0,05 | 0,09 | 0,27 | 0,48 | 0,57 | 1,46 | ||
| -24 | -1,00 | -0,39 | -0,11 | 0,05 | 0,09 | 0,27 | 0,48 | 0,57 | 1,46 | ||
| -24 | -1,00 | -0,39 | -0,11 | 0,05 | 0,09 | 0,27 | 0,48 | 0,57 | 1,46 | ||
| -24 | -1,00 | -0,39 | -0,11 | 0,05 | 0,09 | 0,27 | 0,48 | 0,57 | 1,46 |
Алгоритм сортировки прямым выбором
Блок-схема 1. Процедура сортировки массива методом прямого выбора.
| Прямой выбор |
| Прямой выбор |
| j,A,i |
| A[i],A[j] |
| Findmin |
| Swap |
| Input N, A[1..N] |
| j:=0 to N-1 |
| Swap |
| Swap |
| Input i,j |
| t:=i |
| i:=j |
| j:=t |
| A[u]<min |
| Findmin |
| Findmin |
| Input j,A,i |
| u:=j+1 to N-1 |
| i:=j,min:=A[j] |
| min:=A[u] |
| i:=u |
| нет |
| да |
Текст процедуры для сортировки прямым выбором
procedureFindMin(startindex:integer;M:ar;varlowindex: integer);{Перебирает массив начиная с заданного индекса и находим минимальный элемент}
varmin,u:integer;
Begin
lowindex:= startindex;
min := M[startindex];
foru:=startindex+1 toN-1 do
Begin
inc(Psrav);
ifM[u]< min then
Begin
min := M[u];
lowindex:= u;
end;
end;
end;
…
procedureswap(varx,y,z: integer);{Меняем местами заданные элементы массива}
vart: integer;
Begin
t := x;
x := y;
y := t;
inc(z);
end;
…
procedurePryamoi_vibor(M:Ar);{Сортирует массив с помощью прямого выбора}
Var
j:integer;
Begin
forj:=0 toN-1 do
Begin
FindMin(j,m,i);
swap(M[j],M[i],Pper);
End
end;
Шейкерная сортировка
Разработка алгоритма шейкерной сортировки
Шейкерная сортировка − разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие - к началу. Своим появлением эта сортировка обязан такому недостатку сортировки «пузырьком», при котором «лёгкие пузырьки» всплывают за один проход, а «тяжёлые» − тонут за несколько. Такая ассиметрия и вызвала появление новой сортировки, на каждом шаге которой осуществляется проход как в одну сторону, так и в другую. Таким образом, на каждом шаге «лёгкий пузырёк» всплывает на поверхность, а «тяжёлый» − тонет.
Метод этот получил название шейкерной сортировки.
Таблица 2
| Шаг | Направление движения | Элементы массива | ||||||
| Справа-налево | ||||||||
| Слева-направо | 10 || | |||||||
| Справа-налево | 10 || | || 75 | ||||||
| Слева-направо | 17 || | || 75 | ||||||
| Справа-налево | 17 || | || 70 | ||||||
| Слева-направо | 18 || | || 70 |
Серым цветом в таблице выделена та часть массива, которая исключается из просмотра.
Алгоритм шейкерной сортировки
Блок-схема 2. Процедура шейкерной сортировки массива.
| l:=2; r:=N-1; k:=R |
| Input A[N] |
| Шейкер |
| A1 |
| Шейкер |
| A2 j:=r downto l-1 |
| a[j-1] > a[j] |
| нет |
| да |
| A2 |
| A3 j:=l to r |
| A[j-1] > A[j] |
| нет |
| да |
| A3 |
| r:=k-1 |
| A1 l>r |
| L:=k+1 |
| A[j],A[j-1] |
| Swap |
| k:=j |
| A[j],A[j-1] |
| k:=j |
| Swap |
Текст процедуры шейкерной сортировки
procedureShaker(M:Ar);{Сортирует массив методом смешивания}
Var
j,k,l,r:integer;
Begin
L:=2;
R:=N-1;
k:=R;
Repeat
Begin
forj:=r downtol-1 do
Begin
ifM[j-1] > M[j] then
Begin
swap(M[j],M[j-1],Sper);
k:=j;
end;
inc(Ssrav);
end;
L:=k+1;
forj:=l tor do
Begin
ifM[j-1]> M[j] then
Begin
swap(M[j],M[j-1],Sper);
k:=j;
end;
inc(Ssrav);
end;
r:=k-1;
end;
untilL>R;
end;
Быстрая сортировка
Разработка алгоритма быстрой сортировки
Быстрая сортировка, часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов). Этот улучшенный метод сортировки основан на обмене.
Если количество элементов в массиве не многим меньше максимального их значения, то в данном случае наиболее эффективным и по быстродействию, и по простоте является быстрая сортировка. Основные достоинства этого алгоритма состоят в том, что он точечный (использует лишь небольшой дополнительный стек), в среднем требует только около N log N операций для того, чтобы отсортировать N элементов, и имеет экстремально короткий внутренний цикл. Недостатки алгоритма состоят в том, что он рекурсивен (реализация очень затруднена когда рекурсия недоступна), в худшем случае он требует N2 операций, кроме того он очень "хрупок": небольшая ошибка в реализации, которая легко может пройти незамеченной, может привести к тому, что алгоритм будет работать очень плохо на некоторых файлах.
Основная идея алгоритма быстрой сортировки состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент a[i] такой, что a[i] > x, а затем массив просматривается справа, пока не встретится элемент a[j] такой, что a[j] < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x.
Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. Понятно, что как обычно, рекурсию можно заменить итерациями, если запоминать соответствующие индексы массива. Проследить этот процесс можно на примере таблицы (таблица 2).
Таблица 3
| Начальное состояние массива | 8 23 5 65 44 33 1 6 |
| Шаг 1. (в качестве x выбирается a[4]) | 8 23 5 65 44 33 1 6 |-------------| 8 23 5 6 44 33 1 65 |
| Шаг 2. (в подмассиве a[1..7] за x выбирается a[4]) | 8 23 5 6 44 33 1 65 |-------------------| 1 23 5 6 44 33 8 65 |-----| 1 6 5 23 44 33 8 65 |
| Шаг 3. (в подмассиве a[1..3] в качестве x выбирается a[2]) | 1 6 5 23 44 33 8 65 |--| 1 5 6 23 44 33 8 65 |
| Шаг 4. (в подмассиве a[4..7] в качестве x выбирается a[5]) | 1 5 6 23 44 33 8 65 |-----| 1 5 6 23 8 33 44 65 |
| Шаг 5. (в подмассиве a[4..6] в качестве x выбирается a[5]) | 1 5 6 23 8 33 44 65 |---| 1 5 6 8 23 33 44 65 |
Алгоритм быстрой сортировки массива.
Блок-схема 3. Процедура быстрой сортировки массива
| QSort |
| i:=L,j:=R |
| A1 |
| A1i>j |
| Qsort |
| A[N],L,R |
| i <= j |
| w:=A[(L+R)div 2] |
| A2 A[i]<w |
| A2 |
| inc(i) |
| A3 w <A[j] |
| A3 |
| dec(j) |
| A[i],A[j] |
| inc(i),dec(j) |
| Swap |
| L < j |
| i <R |
| L,j |
| I,R |
| QSort |
| QSort |
| да |
| нет |
| нет |
| нет |
| да |
| да |
Текст процедуры быстрой сортировки
procedureQsort(l,r:integer);{Сортирует массив Быстрой сортировкой}
vari,j,w:integer;
Begin
i := l; j := r;
w := Q[(l+r) div2];
Repeat
while(Q[i] < w) do begininc(i); inc(Qsrav); end;
while(w < Q[j]) do begindec(j); inc(Qsrav); end;
if(i <= j) then
Begin
swap(Q[i],Q[j],Qper);
inc(i); dec(j);
end;
until(i > j);
if(l < j) thenqSort(l,j);
if(i < r) thenqSort(i,r);
end;
Графическая работа
Для того, чтобы изобразить гистограммы и таблицы по полученным данным, воспользуемся процедурами из модулей GraphABC и ABCobjects.
Готовый алгоритм построения гистограмм для значений из массива Q выглядит следующим образом:
ProcedureGist;{Строит гистрограмму одного массива}
Var
a,c,b:integer;
x:real;
Begin
SetBrushColor(clgreen);
Textout(500,5,'Быстрая');
SetBrushColor(clDarkOrchid);
Textout(600,5,'Прямая');
SetBrushColor(clHotPink);
Textout(700,5,'Шейкерная');
SetBrushColor(clmoneygreen);
Textout(95,a+55,'Перемещений');
Textout(355,a+55,'Сравнений');
Textout(605,a+55,'Время в мсек.');
x:=Qper;
Ifx<Pper thenx:=Pper;
Ifx<Sper thenx:=Sper;
a:=round(90/(x/Qper));
b:=round(90/(x/Pper));
c:=round(90/(x/Sper));
SetBrushColor(clgreen);
FillRectangle(10,y+165,70,y+165-a+2);
SetBrushColor(clDarkOrchid);
FillRectangle(100,y+165,160,y+165-b+2);
SetBrushColor(clHotPink);
FillRectangle(190,y+165,250,y+165-c+2);
x:=Qsrav;
Ifx<Psrav thenx:=Psrav;
Ifx<Ssrav thenx:=Ssrav;
a:=round(90/(x/Qsrav));
b:=round(90/(x/Psrav));
c:=round(90/(x/Ssrav));
SetBrushColor(clgreen);
FillRectangle(280,y+165,340,y+165-a+2);
SetBrushColor(clDarkOrchid);
FillRectangle(370,y+165,430,y+165-b+2);
SetBrushColor(clHotPink);
FillRectangle(460,y+165,520,y+165-c+2);
x:=Qtime;
Ifx<Ptime thenx:=Ptime;
Ifx<Stime thenx:=Stime;
a:=round(90/(x/Qtime));
b:=round(90/(x/Ptime));
c:=round(90/(x/Stime));
SetBrushColor(clgreen);
FillRectangle(550,y+165,610,y+165-a+2);
SetBrushColor(clDarkOrchid);
FillRectangle(640,y+165,700,y+165-b+2);
SetBrushColor(clHotPink);
FillRectangle(730,y+165,790,y+165-c+2);
setpencolor(clblack);
SetBrushColor(clmoneygreen);
Textout(10,y+185,inttostr(Qper));
Textout(100,y+185,inttostr(Pper));
Textout(190,y+185,inttostr(Sper));
Textout(280,y+185,inttostr(Qsrav));
Textout(370,y+185,inttostr(Psrav));
Textout(460,y+185,inttostr(Ssrav));
str(Qtime:8:4,Qtimest);
str(Ptime:8:4,Ptimest);
str(Stime:8:4,Stimest);
Textout(550,y+185,Qtimest);
Textout(640,y+185,Ptimest);
Textout(730,y+185,Stimest);
end;