Классическими примерами для демонстрации возможностей массивов являются задачи сортировки и поиска.
Все методы сортировки можно разделить на две большие группы: прямые методы сортировки; улучшенные методы сортировки.
Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы: сортировка обменом ("пузырьковая" сортировка). сортировка выбором (выделением); сортировка вставкой (включением);
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса сортировки.
Принцип метода: Слева направо поочередно сравниваются два соседних элемента, и их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива. После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент ("всплыл" первый "пузырек"). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Всего требуется п-1 проход.
начало А(10) I:=1,9,1 J:=I, 9,1 A(j)>=A(j+1) c:=a(i) a(i):=a(j+1) a(j+1):=c А(10) конец
Program Uses Crt; Const n=5; Var a :array [1..n] of byte; i,j,p :byte; k,c :byte; begin ClrScr; Randomize; n:=5; WriteLn('Исходный массив:'); for i:=1 to n do begin a[i]:=Random(100); {Генерация значений элементов массива} Write(a[i]:3) {Печать элементов массива} end; WriteLn; WriteLn('Сортировка:'); c:=0; {Начальное значение счетчика итераций} for i:=1 to n-1 do {Внешний цикл} begin for j:=i+1 to n do {Внутренний цикл} begin if a[i]>a[j] then {Условие перестановки} begin k:=a[i]; {Переменная для обмена значений элементов} a[i]:=a[j]; {Обмен значений элементов} a[j]:=k {Обмен закончен} end end; for p:=1 to n do Write(a[p]:3); {Цикл печати состояния массива} WriteLn; c:=c+1 {Счетчик итераций} end; WriteLn('Количество итераций: ',c); Write('Отсортированный массив: '); for i:=1 to n do {Цикл печати отсортированного массива} Write(a[i]:3); ReadKey end.
Исходный массив Сортировка: Количество итераций: 4 Отсортированный массив:
Массив данных разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части принимается первый элемент массива.
Таким образом будет иметь место n-1 проход (где n размерность массива), каждый из которых будет включать четыре действия: 1. взятие очередного элемента из неотсортированной части и сохранение в дополнительной переменной; 2. поиск позиции в отсортированной части массива для вставки элемента взятого предыдущим действием, который бы не нарушил порядок; 3. сдвиг элементов массива для вставки элемента массива в отсортированную часть; 4. вставка элемента в найденную позицию.
Program vv22; {Сортировка вставкой. Insertion sort} Uses Crt; Const n=5; Var a :array [1..n] of byte; b,i,j,k,p,c :byte; begin ClrScr; Randomize; {Инициализация генератора случайных чисел} WriteLn('Сортировка методом вставки'); WriteLn('Исходный массив:'); {Генерация и печать исходного массива} for i:=1 to n do begin a[i]:=Random(100); Write(a[i]:3) end; WriteLn;WriteLn; {Перевод двух строк} WriteLn('Сортировка:'); c:=0; {Начальное значение счетчика итераций} for i:=2 to n do {Внешний цикл сортировки} begin b:=a[i]; {Взятие элемента массива из неотсортированной части и сохранение его в дополнительной переменной} j:=1; {Присвоение значения индексной переменной} {Цикл поиска позиции вставки } while b>a[j] do j:=j+1; {Фиксация позиции вставки} for k:=i-1 downto j do a[k+1]:=a[k]; {Цикл сдвига злементов массива для вставки} a[j]:=b; {Вставка элемента массива в найденую позицию} for p:=1 to n do Write(a[p]:3); {Цикл печати итераций сортировки} c:=c+1; {Счетчик итераций} WriteLn end; WriteLn('Количество итераций',c); WriteLn; WriteLn('Отсортированный массив: '); for i:=1 to n do Write(a[i]:3); {Цикл печати отсортированного массива} ReadKey end.
Исходный массив Сортировка: Количество итераций: 4 Отсортированный массив:
Сортировку выбором называют еще сортировкой поиском последовательных миниумов. При первом проходе ищется минимальное значение элементов массива, который затем меняется на первый элемент, затем поиск продолжается на оставшихся. Из оставшихся элементов ищется элемент с минимальным значением и меняется местами с первым из оставшихся, т.е. со вторым элементом исходного массива и т.д.
{Сортировка выбором. Selection sort} Program vv21; Uses Crt; Const n=5; Var v :array [1..n] of byte; i,j,min,imin,c :byte; begin ClrScr; Randomize; WriteLn('Сортировка методом выбора (вставкой)'); WriteLn('Исходный массив:'); {Генерация исходного массива} for i:=1 to n do begin v[i]:=Random(100); Write(v[i]:3) end; WriteLn;WriteLn; WriteLn('Сортировка:'); c:=0; {Начальное значение счетчика итераций} for j:=1 to n-1 do {Внешний цикл сортировки} begin min:=v[j]; imin:=j; for i:=j+1 to n do {Внутренний цикл сортировки} if v[i]
Исходный массив Сортировка: Количество итераций: 4 Отсортированный массив: