- Отсортировать массив по возрастанию (метод выбором - поиск минимального).
Массив A является отсортированным (упорядоченным) по возрастанию, если для всех i из интервала [1..n-1] выполняется условие A[i]<=A[i+1].
Суть этого метода сортировки заключается в следующем:
1. В массиве находим минимальный элемент.
2. Меняем минимальный элемент с первым.
3. В усеченном (исключая первый элемент) массиве находим минимальный элемент.
4. Ставим его на второе место. И так далее n-1 раз.
Пример:
Массив A, исходное состояние 1 3 0 9 2
Процесс сортировки
0: 1 3 0 9 2 min=a[3]=0 Переставляем a[1]<->a[3]
1: 0|3 1 9 2 min=a[3]=1 Переставляем a[2]<->a[3]
2: 0 1|3 9 2 min=a[5]=2 Переставляем a[3]<->a[5]
3: 0 1 2|9 3 min=a[5]=3 Переставляем a[4]<->a[5]
4: 0 1 2 3 9 Готово
Здесь знак | отделяет уже отсортированную часть массива от еще не отсортированной.
Фрагмент программы.
Var buf: integer; {через buf будем менять значения двух элементов массива}
imin:IndexEl; {индекс минимального элемента не отсортированной части массива}
…
Begin
…
{n-1 раз ищем минимальный элемент массива}
for i :=1 to n-1 do
begin
{Ищем минимальный элемент в несортированной части массива (от i-го элемента)}
imin:=i; {imin - это индекс минимального элемента массива}
for j:=i+1 to n do
if A[j]<A[imin] then imin:=j;
{переставляем i-ый и imin-ый элементы}
buf:=A[i];
A[i]:=A[imin];
A[imin]:=buf;
End;
…
- Отсортировать массив (метод пузырька ).
-
если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;
-
при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .
В результате наибольший элемент оказывается в самом верху массива. Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д. Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j-го прохода не проверяются элементы, стоящие на позициях выше j.
1-й способ: for i:=1 to n-1 do for j:=1 to n-i do if A[j]>A[j+1] then begin buf:=A[j]; A[j]:=A[j+1]; A[j+1]:=buf; end; |
2-й способ for i:=n-1 downto 1 do for j:=1 to i do if A[j]>A[j+1] then begin buf:=A[j]; A[j]:=A[j+1]; A[j+1]:=buf; end; |
- Вставить в упорядоченный по возрастанию массив новый элемент таким образом, чтобы сохранилась упорядоченность.
Алгоритм решения задачи следующий:
1. Ищем в массиве тот элемент, который больше вставляемого, – для этого последовательно просматриваем все элементы, начиная с первого.
2. Увеличиваем длину массива на 1.
3. После этого все элементы, стоящие правее от найденного, включая его самого, сдвигаются вправо.
4. На освободившуюся позицию вставляется искомый элемент.
Замечание: если все элементы массива меньше вставляемого, то новый элемент надо вставить в конец массива. Если все элементы массива больше вставляемого, то новый элемент надо вставить в начало массива.
Пример: Надо вставить 5 в массив A: 3 4 7 9
1. Ищем элемент, больший вставляемого. Это элемент A[3]=7.
2. Увеличиваем длину массива на 1.
Получаем массив A: 3 4 7 9 X
3. Сдвигаем элементы, начиная с 3-го, вправо.
Получаем массив A: 3 4 7 7 9
4. В элемент A[3] заносим 5.
Получаем массив: 3 4 5 7 9
Фрагмент программы, реализующей данный алгоритм:
…
read(g); {считываем число, которое надо вставить в массив}
{Ищем элемент больше вставляемого }
k:=1; {k – индекс сравниваемого элемента}
while (k<=n) and (g>=a[k]) do {если k не вышла за границу n, и вставляемый элемент меньше или равен A[k]}
k:=k+1; {то переходим к следующему элементу}
n:=n+1; {Увеличиваем длину массива на 1}
for i:=n downto k+1 do
a[i]:=a[i-1]; {Сдвигаем элементы начиная с k-го вправо}
a[k]:=g; {в A[k] заносим g}
…
Демонстрации
<<Назад
