Сортировка одномерного массива
Рассмотрим два способа сортировки одномерного массива.
1. Сортировка одномерного массива методом «пузырька» (случай сортировки по возрастанию). В массиве находят min элемент и меняют его местами с первым элементом. После этого первый элемент из обработки исключается. Теперь в массиве, начиная уже со второго элемента, вновь находят min элемент и меняют его местами со вторым элементом. Каждый раз число обрабатываемых элементов массива уменьшается на единицу. Процесс повторяется до тех пор, пока весь массив не будет упорядочен (рис. 6.2). Блок-схема алгоритма приведена на рис. 6.1.
| Hачало |
| Ввод ak |
| k=1, n-1 |
| Вывод ak |
| конец |
| p=ak; ak=aj; aj=p |
| ak>aj |
| да |
| нет |
| j=k+1,n-1 |
Рис. 6.1. Блок-схема сортировки одномерного массива методом «пузырька»
| М1 |
| М2 |
| М1 |
| М1 |
| М2 |
| М3 |
| М1 |
| М2 |
| М3 |
| Мn |
| М1 |
| М2 |
| М3 |
| Мn |
| …. |
Рис. 6.2. Сортировка одномерного массива методом «пузырька»
2. Метод линейной сортировки одномерного массива.В методе линейной сортировки сравнивают значения каждой пары соседних элементов:
Если два соседних элемента не упорядочены, то их меняют местами (выполняется перестановка элементов массива). Если не производилось ни одной замены, это означает, что массив упорядочен и вычисления заканчивают. Если не все пары соседних элементов упорядочены сравнение и перестановку проводят снова.
Рассмотрим алгоритм линейной сортировки одномерного массива (рис. 6.3):
1) число k – счетчик для подсчета упорядоченных пар приравнивают нулю;
2) сравнивают первый элемент со вторым, если они не упорядочены то их меняют местами, иначе увеличивают k на 1;
3) сравнивают второй элемент с третьим, если они не упорядочены, тогда их меняют местами, иначе увеличивают k на 1;
4) процесс продолжается до n-1 (n – размерность массива);
5) анализируют значение k:
- если k>=n-1 это означает, что замен не было (т.е. последовательность упорядочена) и вычисления завершают;
- если k<n-1 возвращаются к шагу 1.
Пример. Дан массив а(n) упорядочить его в порядке возрастания методом линейной сортировки, n – размерность массива задается константой в программе.
| Начало |
| Ввод ai |
| k=0 |
| j=1, n-1 |
| k>=n-1 |
| k=k+1 |
| Вывод ai |
| конец |
| да |
| нет |
| p=ai; ai=ai+1; ai+1=p |
 |
| да |
| нет |
| (while, repeat) |
Рис.6.3. Блок-схема метода линейной сортировки одномерного массива
{Сортировка одномерного массива методом «пузырька»}
for k:=1 to n-1 do
for j:=k+1 to n do
if a[k]>a[j] then
begin
p:=a[k];
a[k]:=a[j];
a[j]:=p;
end;
{Метод линейной сортировки одномерного массива}
repeat
k:=0;
for i:=1 to n-1 do
if a[i]>a[i+1] then
begin
p:=a[i];
a[i]:=a[i+1];
a[i+1]:=p;
end
else
k:=k+1;
until k>=n-1;