Сортировка одномерного массива

Сортировка массива

mass[j+1]) then                   begin                      buf := mass[j];                      mass[j] := mass[j+1];                      mass[j+1] := buf;                  end;" width="640"

Сортировка по возрастанию

for i:=1 to n-1 do

     for j:=1 to n-i do

             if (mass[j] mass[j+1]) then

                  begin

                     buf := mass[j];

                     mass[j] := mass[j+1];

                     mass[j+1] := buf;

                 end;

mass[j+1]) then                      begin                          buf := mass[j];                          mass[j] := mass[j+1];                          mass[j+1] := buf;                      end;              end;       writeln;        for i:=1 to n do          write(mass[i], ' | ');       readln; end." width="640"

type

     massiv = array [1..10] of integer;

var

     mass : massiv;

     i , j , n , buf: integer;

begin

     randomize;

     write('Введите длину массива : ');readln(n);

     for i:=1 to n do

         begin

             mass[i] := random(10);

             write(mass[i], ' | ');

         end;

     for i:=1 to n-1 do

         for j:=1 to n-i do

             begin

                 if (mass[j] mass[j+1]) then

                     begin

                         buf := mass[j];

                         mass[j] := mass[j+1];

                         mass[j+1] := buf;

                     end;

             end;

      writeln; 

      for i:=1 to n do

         write(mass[i], ' | ');

      readln;

end.

Метод "пузырька "

Самым простым методом сортировки является так называемый метод " пузырька " . Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:

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

M[i+1] then               swap(M[i],M[i+1]) end;" width="640"

Т екст программы упорядочения массива M[1..N] :

begin    for j:=1 to N-1 do      for i:=1 to N-j do         if M[i] M[i+1] then               swap(M[i],M[i+1]) end;

x[m] then m: = i; { запоминаем значение "m" } b:= x[k]; x[k]:= x[m]; x[m]:= b { переставляем элементы } end;" width="640"

Сортировка выбором

• Основана на определении наибольшего (наименьшего) элемента, который переносится в начало или конец массива в зависимости от вида сортировки ( по возрастанию или по убыванию). Затем эта процедура применяется ко всем оставшимся элементам, кроме уже перемещенных элементов, всего ( N - 1 ) раз. Приведем пример операторов для сортировки элементов массива “Х” по возрастанию:

for j: = 1 to N-1 do begin { цикл по числу "проходов" }

k:= N-j+1; { k - номер последнего элемента в проверяемой части массива }

m:= k; { m - номер элемента с наибольшим значением }

for i:= 1 to N-j do {цикл сравнения элементов в оставшейся части массива}

if x[i] x[m] then m: = i; { запоминаем значение "m" }

b:= x[k]; x[k]:= x[m]; x[m]:= b { переставляем элементы }

end;

x[j] do j:= j+1; { определение номера j для вставки элемента} for k:=i downto j+1 do x[k]:=x[k-1]; { увеличение индексов элементов } x[j]:= b { вставка значения b на место j - го элемента } end;" width="640"

Сортировка вставками

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

for i := 2 to N do begin { цикл по числу шагов }

b:=x[i]; {значение элемента, следующего за отсортированной частью массива}

j:= 1;

while b x[j] do j:= j+1; { определение номера j для вставки элемента}

for k:=i downto j+1 do x[k]:=x[k-1]; { увеличение индексов элементов }

x[j]:= b { вставка значения b на место j - го элемента }

end;