Как отсортировать массив

Самый простой способ — сортировка пузырьком: программа идёт по массиву и меняет местами соседей, которые стоят неправильно. За один проход самый большой элемент «всплывает» в конец, поэтому проходов нужно n - 1.

program BubbleSort;
var
  a: array[1..100] of integer;
  n, i, j, t: integer;
begin
  readln(n);
  for i := 1 to n do
    read(a[i]);
  for i := 1 to n - 1 do
    for j := 1 to n - i do
      if a[j] > a[j + 1] then
      begin
        t := a[j];
        a[j] := a[j + 1];
        a[j + 1] := t;
      end;
  for i := 1 to n do
    write(a[i], ' ');
  writeln;
end.

6
5 2 9 1 5 6

1 2 5 5 6 9

Как это работает:

• внутренний цикл сравнивает a[j] и a[j + 1] и меняет их местами через временную переменную t;
• после i-го прохода последние i элементов уже на своих местах, поэтому внутренний цикл идёт только до n - i — и заодно не выходит за границу: a[j + 1] при j = n - i не дальше a[n];
• обмен двух значений требует третьей переменной: a[j] := a[j + 1]; a[j + 1] := a[j] записал бы в оба элемента одно и то же.

По убыванию — поменяйте знак сравнения: if a[j] < a[j + 1] then.

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

Другой школьный способ: найти наименьший элемент и поставить его на первое место, из оставшихся — на второе и так далее.

for i := 1 to n - 1 do
begin
  minI := i;
  for j := i + 1 to n do
    if a[j] < a[minI] then
      minI := j;
  t := a[i];
  a[i] := a[minI];
  a[minI] := t;
end;

Переменную minI нужно описать в var вместе с остальными. Обменов здесь не больше n - 1 — меньше, чем у пузырька.

Если элементов много

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

В PascalABC.NET для динамических массивов (array of integer — размер задаётся во время работы программы) есть готовая процедура Sort(a). В классическом Pascal готовой процедуры сортировки нет, и на контрольных обычно просят написать сортировку самому.

Подводные камни

• Граница внутреннего цикла. for j := 1 to n do с a[j + 1] выходит за конец массива.
• Сортировка строк работает так же — строки сравниваются по алфавиту, точнее по кодам символов. Большие буквы при этом идут раньше маленьких.