Программы сортировки

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

Пример одномерного массива:

var

  A: array[1..5] of integer;

Здесь массив A состоит из пяти целых чисел. Индексация начинается с 1, если не указано иное (в отличие от Python, где индексация — с 0).

Присвоим значения:

A[1] := 7;

A[2] := 2;

A[3] := 5;

A[4] := 9;

A[5] := 1;

Важно помнить: в Pascal можно задать  любую начальную и конечную границу массива, например: array[0..9] или array[-3..3].

Почему массивы важны для ЕГЭ по информатике

В заданиях ЕГЭ массивы встречаются регулярно: в них нужно находить максимальные и минимальные элементы, подсчитывать количество значений, удовлетворяющих условиям, сортировать или фильтровать данные. Уверенное владение массивами — основа успешной подготовки к ЕГЭ по информатике.

Программы сортировки — неотъемлемая часть анализа

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

Оценка сложности сортировки

Каждый алгоритм имеет свою асимптотическую сложность — показатель эффективности в зависимости от количества элементов n.

Обозначается через O:

• O(1) — постоянное время

• O(n) — линейное

• O(n²) — квадратичное

• O(n log n) — логарифмическое

В ЕГЭ важно понимать: простые сортировки работают медленно при больших массивах (O(n²)), а более сложные справляются быстрее (O(n log n)).

Популярные программы сортировки

Ниже рассмотрим основные алгоритмы сортировки с примерами на Pascal. Это поможет лучше понять их механику и научиться применять в заданиях ЕГЭ.

1. Сортировка пузырьком (называется забавно, но все же это Bubble Sort)

Принцип: сравниваем соседние элементы и меняем местами, если они стоят неправильно. Повторяем, пока массив не будет отсортирован.

for i := 1 to N - 1 do

  for j := 1 to N - i do

    if A[j] > A[j + 1] then

    begin

      temp := A[j];

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

      A[j + 1] := temp;

    end;

• Прост в понимании

• Сложность: O(n²)

• Эффективен только на малых массивах

2. Сортировка вставками (также носит название Insertion Sort)

Принцип: каждый элемент вставляется на своё место среди уже отсортированных элементов слева.

for i := 2 to N do

begin

  temp := A[i];

  j := i - 1;

  while (j > 0) and (A[j] > temp) do

  begin

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

    j := j - 1;

  end;

  A[j + 1] := temp;

end;

• Хорош на почти отсортированных массивах

• Сложность: O(n²)

3. Сортировка выбором (оригинальное название на английском: Selection Sort)

Принцип: находим минимальный элемент и ставим его на первую неотсортированную позицию.

for i := 1 to N - 1 do

begin

  minIndex := i;

  for j := i + 1 to N do

    if A[j] < A[minIndex] then

      minIndex := j;

  temp := A[i];

  A[i] := A[minIndex];

  A[minIndex] := temp;

end;

• Работает одинаково медленно при любом вводе

• Сложность: O(n²)

4. Быстрая сортировка (по-простому её называют Quick Sort)

Принцип: выбираем опорный элемент, делим массив, рекурсивно сортируем части.

procedure QuickSort(l, r: integer);

var

  i, j, x, y: integer;

begin

  i := l;

  j := r;

  x := A[(l + r) div 2];

  repeat

    while A[i] < x do inc(i);

    while A[j] > x do dec(j);

    if i <= j then

    begin

      y := A[i];

      A[i] := A[j];

      A[j] := y;

      inc(i);

      dec(j);

    end;

  until i > j;

  if l < j then QuickSort(l, j);

  if i < r then QuickSort(i, r);

end;

• Эффективна и быстра

• Сложность: O(n log n) в среднем, O(n²) в худшем случае

5. Сортировка слиянием (она же - Merge Sort)

Принцип: делим массив пополам, сортируем каждую часть, потом объединяем.

Из-за сложности кода обычно используется в виде встроенной функции. В рамках ЕГЭ чаще применяются более простые сортировки.

6. Пирамидальная сортировка (в оригинале называется Heap Sort)

Принцип: строится куча, затем из неё извлекается наибольший элемент, и массив восстанавливается.

Требует детальной реализации бинарной кучи, редко встречается в школьной программе, но полезна для общего развития.

Сравнительная таблица сортировок

Какую сортировку использовать на ЕГЭ?

На практике, при решении заданий ЕГЭ, чаще всего достаточно использовать простые сортировки, особенно если объём данных невелик. Иногда в Pascal можно использовать стандартные процедуры сортировки, если это не запрещено в условии.

Главное — понимать принципы сортировки, уметь самостоятельно реализовать алгоритм и объяснить его логику.

Советы по подготовке к ЕГЭ

• Освой работу с массивами: перебор, поиск, условная обработка, сортировка.

• Разбирайся в индексах: не путай порядковый номер и значение!

• Пробуй реализовать сортировки сам: особенно пузырьковую и вставками.

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

• Решай типовые задачи ЕГЭ и тестовые в том числе. Они представлены ниже.

Вопрос 1.

Какой индекс имеет первый элемент массива, объявленного так:

var A: array[3..10] of integer;

A) 0

B) 1

C) 3

D) 10

Вопрос 2.

Что делает данный фрагмент кода?

for i := 1 to N - 1 do

  for j := 1 to N - i do

    if A[j] > A[j + 1] then

    begin

      temp := A[j];

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

      A[j + 1] := temp;

    end;

A) Ищет максимальный элемент массива

B) Выполняет сортировку пузырьком 

C) Считает количество чётных чисел

D) Переворачивает массив

Вопрос 3.

Какой из алгоритмов сортировки имеет среднюю сложность O(n log n)?

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

B) Сортировка пузырьком

C) Быстрая сортировка 

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

Вопрос 4.

Какой тип ошибки может возникнуть, если попытаться обратиться к элементу массива за пределами диапазона?

A) Syntax Error

B) Runtime Error 

C) Logic Error

D) Compilation Error

Вопрос 5.

Что делает следующий код?

min := A[1];

for i := 2 to 10 do

  if A[i] < min then

    min := A[i];

A) Находит сумму всех элементов массива

B) Сортирует массив по убыванию

C) Находит максимальный элемент

D) Находит минимальный элемент.