Pascal. Сортировка одномерных массивов

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

То есть, если у нас 10 чисел, то сначала первое из них будет сравниваться до тех пор, пока не будет найдено другой, например, большее его (если мы сортируем просто по возрастанию). Далее так же будет сравниваться 2, 3, 4 … элементы с последующими, но не с теми, которые уже отсортированы.

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

Program SortMas;
var
 i, j, k: integer; 
  mas: array[1..20] of integer; 
Begin
  randomize; 
  for i := 1 to 20 do mas[i] := random(100);
  writeln;
  writeln('массив до сортировки');
  for i := 1 to 20 do write(mas[ i], ' '); 
  for i := 1 to 19 do 
    for j := i + 1 to 20 do 
      if mas[i] < mas[j] then 
      begin
        k := mas[i];
        mas[i] := mas[j];
        mas[j] := k; 
      end;
  writeln('массив после сортировки');
  for i := 1 to 20 do write(mas[ i], ' '); 
End.

Обратите внимание на 2 первые строки после Begin. Здесь мы вызываем процедуру генерации случайных чисел. То есть просто заполняем наш массив числами от 1 до 100. Далее в цикле выводится для пользователя первоначальный массив.

Далее следует сам алгоритм сортировки, для новичков объясним, что это 2 цикла for, первый из них, в данной случае, идет с самого начала и до N-1 (1 первого до предпоследнего элемента).

Далее вложенный for, где используется уже другой счетчик j. Он изменяется от текущего i-того, увеличенного на 1 и до конца. И далее мы проверяем 2 элемента массива в условии и, если все нас устраивает, то производим обмен переменными. В последнем цикле мы выводим отсортированный массив.

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

Program SortPopolam;
var
  i, j, k: integer; 
  mas: array[1..10] of integer; 
begin
  randomize; 
  for i := 1 to 10 do mas[i] := random(101);
  writeln('массив до сортировки');
  for i := 1 to 10 do write(mas[ i], ' '); 
  for i := 1 to 4 do 
    for j := i + 1 to 5 do 
      if mas[ i] > mas[ j] then 
      begin
        k := mas[ i];
        mas[i] := mas[j];
        mas[j] := k; 
      end;
  for i := 5 to 9 do 
    for j := i + 1 to 10 do 
      if mas[ i] < mas[ j] then 
      begin
        k := mas[ i];
        mas[ i] := mas[j];
        mas[j] := k; 
      end;
  writeln;
  writeln('массив после сортировки');
  for i := 1 to 10 do write(mas[ i], ' '); 
end.

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

Как видите, здесь нет ничего особенного. И еще один пример по сортировке выбором. Пусть нудно отсортировать массив таким образом, чтобы числа в нем располагались в порядке возрастания своих последних разрядов. Допустим, если у нас массив 17 23 18 70, то после сортировки он должен выглядеть так: 70 23 17 18. Вот код этой программы.

Program SortOstatok;
var
  a: array[1..10] of Integer; 
  i, j, k: Integer; 
begin
 randomize;
  for i := 1 to 10 do a[ i] := random(100); 
  writeln('массив до сортировки');
  for i := 1 to 10 do write(a[ i], ' '); 
  for i := 1 to 9 do 
    for j := i + 1 to 10 do 
      if a[i] mod 10 > a[j] mod 10 then begin
        k := a[i];
        a[i] := a[j];
        a[j] := k;
      end;
  writeln('массив после сортировки');
  for i := 1 to 10 do write(a[i], ' '); 
end.

Эта программа схожа с первой, их отличие лишь в том, что разное условие для перестановки элементов массива. В первой это «if mas[i] < mas[j] then «, а во втрой «if a[i] mod 10 > a[j] mod 10 then» То есть мы располагаем наши элементы в таком необычном порядке благодаря тому, что просто проверяем остатки их деления на 10, то есть и сравниваем их последние цифры.

Теперь подробнее о сортировке пузырьком. Его сущность заключается в том, что мы сравниваем соседние элементы парами : 1 и 2, 2и 3,3 и 4,4 т.д. И если наш элемент удовлетворяет условию сортировки, то мы его проталкиваем в конец массива, он как бы всплывает, прямо как «пузырек». От этого и название этого алгоритма.

Вот пример программы с этим алгоритмом.

Program SortPusirkom;
var
  mas: array[1..20] of integer;
  i, j, k: integer; 
begin
  randomize;
  for i := 1 to 20 do mas[i] := random(100); 
  writeln('массив до сортировки');
  for i := 1 to 20 do write(mas[ i], ' '); 
  for i := 1 to 19 do
    for j := 1 to 20 - i do
     if mas[j] > mas[j + 1] then begin
        k := mas[j];
        mas[j] := mas[j + 1];
        mas[j + 1] := k;
      end;
  writeln;
  writeln('Отсортированный массив: ');
  for i := 1 to 20 do
    write(mas[i], ' ');
end.

Ее алгоритм чем-то похож на сортировку выбором. Здесь так же 2 цикла for, но второй цикл идет с 1 до 20 — i.

Кроме того существует второй, не менее известный алгоритм сортировки «пузырьком» с флагом. Флаг — это переменная типа boolean. Из-за этого меняется структура алгоритма, но сущность остается прежней. Вот он.

program SotrSFlagom;
var
  a: array[1..20] of integer;
  i, j, L: integer;flag: boolean;
begin
  randomize;
  for i := 1 to 20 do
    a[i] := random(100);
  writeln('массив до сортировки');
  for i := 1 to 20 do write(a[i], ' ');
  i:=0;
  repeat
    i := i + 1;
    flag:=false;
    for j := 19 downto i do
      if a[j] < a[j + 1] then begin
        L := a[j]; a[j] := a[j + 1]; a[j + 1] := L;
        flag := true;
      end;
  until not flag;
  writeln;
  writeln('массив после сортировки');
  for i := 1 to 20 do write(a[i], ' ');
end.

Этот алгоритм наиболее сложный для запоминания, но уверяю Вас, что его и не нужно зазубривать, а понимать, что за чем идет. Здесь используется внешний цикл repeat … until not flag; Он существует до тех пор, пока флаг не окажется истинным, то есть flag := true; А это может произойти, если наше условие сортировки выполняется. И наш элемент тоже всплывает, как пузырек.

Итак, надеюсь, что вы поняли, в чем отличие этих 2 алгоритмов сортировок и теперь сможете отсортировать любой массив так, как Вам нужно.

Рейтинг
( 1 оценка, среднее 5 из 5 )
Загрузка ...