Алгоритм обменной сортировки
Простая обменная сортировка [в просторечии называемая "методом пузырька"] для массива M[0], M[1], ..., M[n-1] работает следующим образом. Начиная с конца массива сравниваются два соседних элемента [M[n-1] и M[n-2]]. Если выполняется условие M[n-2] > M[n-1], то значения элементов меняются местами. Процесс продолжается для M[n-2] и M[n-3] и т.д., пока не будет произведено сравнение M[1] и M[0]. Понятно, что после этого на месте M[0] окажется элемент массива с наименьшим значением. На втором шаге процесс повторяется, но последними сравниваются M[2] и M[1]. И так далее. На последнем шаге будут сравниваться только текущие значения M[n-1] и M[n-2]. Понятна аналогия с пузырьком, поскольку наименьшие элементы [самые "легкие"] постепенно "всплывают" к верхней границе массива. Ниже приведен пример реализации алгоритма простой обменной сортировки:
Общий алгоритм
function Grade (Array[], LengthOfArray) {
if (LengthOfArray < 2) then return Array[]
else {
LimitIndex:=1;
while (LimitIndex < LengthOfArray) do {
CurrentIndex:= LengthOfArray-1;
while (CurrentIndex > LimitIndex) do {
if (Array[CurrentIndex-1] > Array[CurrentIndex]) then {
Temp:= Array[CurrentIndex-1];
Array[CurrentIndex-1]:= Array[CurrentIndex];
Array[CurrentIndex]:=Temp;
}
CurrentIndex:= CurrentIndex-1;
}
LimitIndex:= LimitIndex+1;
}
return Array[];
}
}
Pascal
program primer;
const n=5;
var a: array [1..n] of integer;
i, currentIndex, limitIndex, temp: integer;
begin
// заполнение массива случайными целыми числами от 10 до 99
randomize;
for i:=1 to n do begin
a[i]:=trunc((99-10)*random+10);
end;
// вывод исходного массива
write('Исходный массив: ');
for i:=1 to n do begin
write ('a[', i, ']=>', a[i]:3, '; ');
end;
writeln;
// обменная сортировка
if not (n<2) then begin
limitIndex:=1;
while (limitIndex<=n) do begin
currentIndex:=n;
while (currentIndex>limitIndex) do begin
if (a[currentIndex-1]>a[currentIndex]) then begin
temp:=a[currentIndex-1];
a[currentIndex-1]:=a[currentIndex];
a[currentIndex]:=temp;
end;
dec(currentIndex);
end;
inc(limitIndex);
end;
end;
// вывод отсортированного массива
write('Отсортированный массив: ');
for i:=1 to n do begin
write ('a[', i, ']=>', a[i]:3, '; ');
end;
writeln;writeln;
end.