СОРТИРОВКА ЭЛЕМЕНТОВ МАССИВА

СОРТИРОВКА ЭЛЕМЕНТОВ МАССИВА

При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, т.е. упорядочивания. Это значит, что элементы нужно расположить строго по порядку.

Элементы массива можно сортировать:

· по возрастанию — каждый следующий элемент больше предыдущего — А[1] < А[2] <... < A[N];

· по не убыванию — каждый следующий элемент не меньше предыдущего, то есть больше или равен А[1 ] ≤ А[2] ≤... ≤A[N];

· по убыванию — каждый следующий элемент меньше предыдущего А[1 ] > А[2] > ... > A[N];

· по не возрастанию — каждый следующий элемент не больше предыдущего, то есть меньше или равен А[1] ≥ А[2] ≥ ... ≥ A[N].

Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки.

Достаточно простой для понимания является сортировка методом пузырька, который также называют методом простого обмена.

Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).

Метод пузырька (простой обмен):

• При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.

Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.

• При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.

• На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.

• В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.

• После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно n-1, где n – это количество элементов массива.

• Количество сравнений в каждом проходе равно n-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).

• При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.

program sort1;

const

mn = 10;

var

a: array[1..mn] of integer;

i, j, k,n: integer;

begin
readln(n);

randomize;

for i := 1 to n do

begin

a[i] := random(256);

write (a[i]:4);

end;

writeln;

for i := 1 to n-1 do

for j := i+1 to n do

if a[i] > a[j] then

begin

k := a[i];

a[i] := a[j];

a[j] := k

end;

for i := 1 to n do

write (a[i]:4);

end.

12 Следующая ⇒