Записи теоретических кусков

Квадратичные сортировки

Постановка задачи

Одной из самых важных задач в информатике является задача сортировки произвольного набора элементов с заданных на ним порядком.

Например, пусть у нас имеется массив из $n$ чисел. Напомним, что объявление и считывание массива на паскале выглядит как-то так: 

1
2
3
4
5
6
7
8
9
var
  a: array [1..1000] of integer; 
  // массив из не более чем 1000 целых чисел
  n, i: integer;

begin
  read(n); // считываем количество чисел
  for i := 1 to n do 
    read(a[i]); // считываем элементы массива

Итак, пусть нам ввели какие-нибудь числа. Скажем, 4 -5 9 2 7 1 6. При этом a[1] = 4, a[2] = -5 и т. д.

Наша задача: переупорядочить числа таким образом, чтобы они шли по возрастанию, если читать их слева направо. Иными словами, нам нужно написать код, после которого числа массива a будут лежать в такой последовательности: -5 1 2 4 6 7 9.

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

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

Проиллюстрируем сказанное выше кодом. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
var
  a: array [1..1000] of integer; 
  n, i, min_element: integer;

begin
  // предположим, что массив a уже считан
  min_element := a[1];
  for i := 2 to n do 
    if min_element > a[i] then 
      min_element := a[i];
  writeln('Minimum in array: ', min_element);

Используя сакральное знание о том, как искать минимум, мы можем предложить следующий алгоритм сортировки:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var
  a: array [1..1000] of integer;
  i, j, index_of_min_element, n: integer;
  temp: integer; // временная переменная для обмена значениями

begin
  read(n);
  for i := 1 to n do
    read(a[i]);
  
  for i := 1 to n - 1 do begin 
    // необходимо n - 1 раз выбрать минимум среди элементов 
    // a[i], a[i + 1], ..., a[n] и обменять его с элементом a[i] местами
    index_of_min_element := i;
    for j := i + 1 to n do
      if a[index_of_min_element] > a[j] then
        index_of_min_element := j;
    temp := a[index_of_min_element];
    a[index_of_min_element] := a[i];
    a[i] := temp;
  end;

  for i := 1 to n do
    write(a[i], ' ');
  writeln;
end.

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var
  a: array [1..1000] of integer;
  i, j, n: integer;
  temp: integer; // временная переменная для обмена значениями

begin
  read(n);
  for i := 1 to n do
    read(a[i]);
  
  for i := 1 to n - 1 do begin 
    for j := 1 to n - 1 do 
      if a[j] > a[j + 1] then begin
        temp := a[j];
        a[j] := a[j + 1];
        a[j + 1] := temp;
      end;
  end;

  for i := 1 to n do
    write(a[i], ' ');
  writeln;
end.

Приведём венгерский народный танец «сортировка пузырьком», который иллюстрирует рассматриваемый нами алгоритм.

Время работы

Основные операции в алгоритме сортировки пузырьком происходят в строках 13-17. Эти строки выполняются в двойном цикле от $1$ до $n$. Отсюда следует, что время работы сортировки пузырьком есть $O(n^2)$. Это значит, что сортировка пузырьком применима на массивах размера $10^4$, но неприменима на массивах порядка $10^5$.