Тема 1.4. Сортировки

Цель.

Овладеть различными методами упорядочивания данных, отличающимися как по скорости, так и по используемой памяти. Умение оценивать сложность алгоритма.

Основные понятия.

Ключевые слова.

ПРИМЕР.

Обменная сортировка (пузырьком). Дан массив целых чисел из N элементов. Упорядочить элементы в порядке не убывания путём сравнения пар соседних элементов.

Алгоритм.

Будем сравнивать последовательно пары соседей. Если они стоят не правильно, меняем их местами. Пройдя один раз от начала до конца, мы получим правильно стоящий последний элемент (самый большой). Организуем второй, третий и т.д. проходы, пока все элементы не станут в нужном порядке. Максимальное количество проходов – N-1.

Решение.

// C++

# include <iostream>

# include <cstdlib>

using namespace std;

const int N = 10;

int main () // основная часть программы – главная функция

{

setlocale (LC_ALL, "RUS");

cout << "Обменная сортировка (пузырьком)" << endl;

cout << "Ведите количество, потом числа " << endl;

int a [N], n;

cin >> n;

for ( int i=0; i < n; i++ )

cin >> a [i];

for ( int i=1; i < n; i++ )

for ( int j=0; j < n-i; j++ )

if ( a [j] > a [j+1] )

swap (a [j], a [j+1]);

for ( int i=0; i < n; i++ )

cout << a [i] << " ";

cout << endl;

system ("PAUSE");

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.WriteLine ("Обменная сортировка (пузырьком)");

Console.WriteLine ("Ведите количество, потом числа по 1 в строке");

int n = int.Parse (Console.ReadLine ());

int [] a = new int [n];

for ( int i=0; i < n; i++ ) // каждое число в отдельной строке

a [i] = int.Parse (Console.ReadLine ());

for ( int i=1; i < n; i++ )

for ( int j=0; j < n-i; j++ )

if ( a [j] > a [j+1] )

{

int temp = a [j];

a [j] = a [j+1];

a [j+1] = temp;

}

for ( int i=0; i < n; i++ ) // печатаем числа в отдельных строках

Console.WriteLine (a [i]);

Console.ReadKey ();

}

}

Задачи для обязательного решения.

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

Исходные данные:

17

11 17 -100 1 2 3 7 8 7 8 0 1 2 3 99 -99 -1000000

Результат:

-1000000 -100 -99 0 1 1 2 2 3 3 7 7 8 8 11 17 99

1.4.1.1. Сортировка вставкой. Массив вводится по элементам, и каждый элемент сразу ставится на своё место в нужном порядке, т.е. ищется его место, начиная с конца, все большие элементы сдвигаются к концу.

1.4.1.2. Сортировка поиском МИН (МАХ). Упорядочить массив путём поиска нужного элемента на каждое очередное место.

1.4.1.3. Быстрая сортировка. На каждом этапе массив разбивается на две части относительно некоторого центрального значения: слева стоят все меньшие его, справа – все большие или равные. На каждую половинку рекурсивно запускаем аналогичную процедуру. Разбиение заканчивается, когда размер очередного фрагмента становится не больше 2. Тогда два элемента можно переставить в результате одного сравнения.

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

1.4.1.5. Сортировка поразрядная. Дан массив из nнеотрицательных целых чисел. Расположить его элементы в порядке возрастания, используя 10 вспомогательных массивов такого же размера.

1.4.1.8. Слияние 2-х упорядоченных массивов. Даны два массива целых чисел из nиmэлементов. Слить оба массива в новый изn+mэлементов, пройдя по каждому исходному массиву от начала до конца по одному разу.

1.4.1.7. Использовать стандартную функцию сортировки для упорядочивания массива целых чисел.

Задачи для самостоятельного решения.

1.4.2.1. Слияние 3-х упорядоченных массивов. Даны три массива целых чисел из k,nиmэлементов. Слить все три массива в новый изk+n+mэлементов, пройдя по каждому исходному массиву от начала до конца по одному разу. В первой строке задаётся размер первого массиваn, во второй строке – сам массив. Второй и третий массивы заданы таким же образом. Вывести массив-результат.

Исходные данные:

4

1 2 5 6

6

1 3 5 7 7 9

5

1 2 3 4 5

Результат:

1 1 1 2 2 3 3 4 5 5 5 6 7 7 9

1.4.2.2, Поиск пересечения 2-х упорядоченных массивов. Даны два массива целых чисел из nиmэлементов. Выбрать в новый массив те элементы, которые есть в обоих исходных массивах, пройдя по каждому исходному массиву от начала до конца по одному разу. В первой строке задаётся размер первого массиваn, во второй строке – сам массив. Второй массив задан таким же образом. Вывести массив-результат.

Исходные данные:

4

1 2 5 6

6

1 3 5 7 7 9

Результат:

1 5

1.4.2.3. Поиск разности 2-х упорядоченных массивов. Даны два массива целых чисел из nиmэлементов. Выбрать в новый массив те элементы, которые есть в первом массиве и отсутствуют во втором, пройдя по каждому исходному массиву от начала до конца по одному разу. В первой строке задаётся размер первого массиваn, во второй строке – сам массив. Второй массив задан таким же образом. Вывести массив-результат.

Исходные данные:

4

1 2 5 6

6

1 3 5 7 7 9

Результат:

2 6

1.4.2.4. Параллельная сортировка. Даны два целочисленных массива из nэлементов. Упорядочить элементы первого массива по возрастанию, параллельно переставляя соответствующие элементы и второго массива. В первой строке задаётся размер каждого массиваn, во второй и третьей строке – сами массив. Вывести массивы-результаты.

Исходные данные:

6

3 1 2 5 4 6

1 3 5 7 8 9

Результат:

1 2 3 4 5 6

3 5 1 8 7 9

1.4.2.5. Лексикографическая сортировка строк. Дан массив символьных строк. Напечатать эти строки в словарном порядке. В первой строке задаётся количество строк n, во второй и далее – сортируемые строки. Вывести упорядоченные строки.

Исходные данные:

4

пример

простого

лёгкого

текста

Результат:

лёгкого

пример

простого

текста

1.4.2.6. Двоичный поиск значения в упорядоченном массиве. Дан упорядоченный по возрастанию массив из nцелых чисел и некоторое целое значениеx. Напечатать номер элемента массива, который совпадает с заданным значением. Если таких элементов нет, напечатать -1. В первой строке задаётся размер массиваn, во второй строке – сам массив. В третьей строке – искомое значение.

Исходные данные:

6

1 3 5 7 7 9

4

Результат:

-1

1.4.2.7. Расстояние Хэмминга. В связи с особенностями линии связи, используемой для передачи сообщений из пункта A в пункт B, каждый бит принятого сообщения с вероятностью 0.001 содержит ошибку. Из пункта A в пункт B было послано одно из n сообщений m₁, m₂, ..., m_n. В пункте B было принято сообщение s. Ваша задача заключается в определении наиболее вероятного исходного сообщения. Очевидно, что оно будет одним из тех сообщений, расстояние Хэмминга между которым и строкой s минимально. Расстоянием Хэмминга двух строк a и b одинаковой длины называется количество позиций, в которых эти строки различаются (количество элементов в множестве {i | 1 ≤ i ≤ |a|, a_i≠ b_i}).

Первая строка содержит s — принятое сообщение. Вторая строка содержит целое число n — количество сообщений, которые могли быть отправлены. Следующие n строк содержат m_i— эти сообщения. Длины всех сообщений равны (|s| = |m₁| = |m₂| = ... = |m_n|). Сообщения состоят только из символов 0 и 1. Размер входного файла не превосходит 60 Кб.

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

Исходные данные:

010101 3 110011 011001 000111

Результат:

2

2 3

1.4.2.8. Пересечение множеств. Даны два неупорядоченных набора целых чисел (может быть, с повторениями). Выдать без повторений в порядке возрастания все те числа, которые встречаются в обоих наборах. В первой строке записано через пробел два целых числа N и М (1 ≤ N, М ≤ 10⁶) — количество элементов первого и второго наборов, соответственно. В следующих строках записано сначала N чисел первого набора, а затем M чисел второго набора. Числа разделены пробелами или символами конца строки. Каждое из этих чисел попадает в промежуток от 0 до 10⁵. Вывесим в возрастающем порядке без повторений все числа, которые входят как в первый, так и во второй набор. Числа разделять одним пробелом. Если таких чисел нет, то выходной файл должен оставаться пустым.

Исходные данные:

11 6 2 4 6 8 10 12 10 8 6 4 2 3 6 9 12 15 18

Результат:

6 12

1.4.2.9. Преобразование последовательности. Задана последовательность, содержащая n целых чисел. Необходимо найти число, которое встречается в этой последовательности наибольшее количество раз, а если таких чисел несколько, то найти минимальное из них, и после этого переместить все такие числа в конец заданной последовательности. Порядок расположения остальных чисел должен остаться без изменения. Например, последовательность 1, 2, 3, 2, 3, 1, 2 после преобразования должна превратиться в последовательность 1, 3, 3, 1, 2, 2, 2. Написать программу, которая решает данную задачу.

Первая строка содержит число n — количество чисел во входной последовательности (3 ≤ n ≤ 200000). Следующая строка содержит входную последовательность, состоящую из n целых чисел, не превышающих по модулю 10⁶. Все числа в строке разделены пробелом.

Выводится последовательность чисел, которая получается в результате названного преобразования. Все числа в последовательности должны быть разделены пробелом.

Исходные данные:

7 1 2 3 2 3 1 2

Результат:

1 3 3 1 2 2 2

1.4.2.10. Несоставляемое число. Дано N натуральных чисел. Требуется найти минимальное натуральное число, не представимое суммой никаких из этих чисел, если в эту сумму каждое исходное число может входить не более одного раза. В первой строке содержит натуральное число N, не превосходящее 10⁴, далее следуют N строк, в каждой из которых записано по одному натуральному числу, каждое из которых не превосходит 10⁹.

Исходные данные:

4 1 1 1 5

Результат:

4

1.4.2.11. Плавающие числа. Дано N целых чисел. Каждое из них можно один раз изменить не более чем на целую величину L как в сторону увеличения, так и в сторону уменьшения или оставить без изменения. Если после такой операции некоторые из чисел оказываются равными, то они засчитываются за одно. С данными числами произвели указанную операцию таким образом, что осталось минимально возможное количество чисел. Написать программу для определения этого количества. В первой строке находятся натуральные числа L и N (N<=100, L<=3200), во второй строке N чисел (в диапазоне от -32000 до 32000), записанных через пробел.

Исходные данные:

5 3 6 10 27

Результат:

2

1.4.2.12. Число в последовательности. Последовательность 011212201220200112… строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д.

Требуется написать программу, которая по заданному натуральному числу N определяет, какое число стоит на N-ом месте. Вводится число N (1 <= N <= 2147483647).

Исходные данные:

10

Результат:

2

1.4.2.13. Музей. В музее регистрируется в течение суток время прихода и ухода каждого посетителя. Таким образом, за день получено N пар значений, где первое значение в паре показывает время прихода посетителя и второе значение - время его ухода. Требуется найти максимальное число посетителей, которые находились в музее одновременно.

В первой строке записано натуральное число N (N < 10⁵) – количество зафиксированных посетителей в музее в течении суток. Далее, идут N строк с информацией о времени визитов посетителей: в каждой строке располагается отрезок времени посещения в формате «ЧЧ:ММ ЧЧ:ММ» (00:00 ≤ ЧЧ:ММ ≤ 23:59). Вывести одно целое число — максимальное количество посетителей, одновременно находящихся в музее.

Исходные данные:

6 09:00 10:07 10:20 11:35 12:00 17:00 11:00 11:30 11:20 12:30 11:30 18:15

Результат:

4

1.4.2.14. Точки и отрезки. Дано N отрезков на числовой прямой и M точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам она принадлежит. Точка x считается принадлежащей отрезку с концами a и b, если выполняется двойное неравенство min(a, b) <= x <= max(a, b). Первая строка содержит два целых числа N – число отрезков и M – число точек (1 <= N, M <= 10⁵). В следующих N строках по два целых числа a_iи b_i– координаты концов соответствующего отрезка. В последней строке M целых чисел – координаты точек. Все числа во входном файле не превосходят по модулю 10⁹. Вывести M чисел – для каждой точки количество отрезков, в которых она содержится.

Исходные данные:

3 2 0 5 -3 2 7 10 1 6

Результат:

2 0

1.4.2.15. Кассы. На одном из московских вокзалов билеты продают N касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.

В первой строке располагается одно целое число N (0 < N <= 1000). В каждой из следующих N строк через пробел расположены 4 целых числа, первые два из которых обозначают время открытия кассы в часах и минутах (часы — целое число от 0 до 23, минуты — целое число от 0 до 59), остальные два — время закрытия в том же формате. Числа разделены пробелами. Время открытия означает, что в соответствующую ему минуту касса уже работает, а время закрытия — что в соответствующую минуту касса уже не работает. Например, касса, открытая с 10 ч 30 мин до 18 ч 30 мин, ежесуточно работает 480 минут. Если времена открытия и закрытия совпадают, то это означает, что касса работает круглосуточно. Если первое время больше второго, то это означает, что касса начинает работу до полуночи, а заканчивает — на следующий день.

Вывести одно число — суммарное время за сутки (в минутах), на протяжении которого работают все N касс.

Исходные данные:

3 1 0 23 0 12 0 12 0 22 0 2 0

Результат:

120

1.4.2.16. Дан массив целых числе. Переставить его элементы так, чтобы их квадраты шли в порядке не убывания. Первая строка содержит число n — количество чисел во входной последовательности (3 ≤ n ≤ 200000). Следующая строка содержит входную последовательность, состоящую из n целых чисел и разделённых одним пробелом. Напечатать упорядоченный массив. Если решение неоднозначно – найти любое.

Исходные данные:

11

-2 -2 -1 0 0 0 2 2 3 3 5

0

Результат:

0 0 0 -1 2 -2 -2 2 3 3 5

Продвинутые задачки.

1.4.3.1. Сортировка слиянием. На каждом этапе большой массив разбивается на две части, каждая из которых отдельно упорядочивается (сортируется). Потом обе части снова сливаются в единый (уже упорядоченный) массив за один проход. К каждой части применяется та же процедура. Разбиение продолжается до тех пор, пока в массиве не останется только два элемента, которые упорядочиваются за одно сравнение.

1.4.3.2. Множество М. Вычислить и напечатать первые n( <=10000) элементов множестваMв порядке возрастания.

Определение множества М:

1) 1 принадлежит M;

2) если число xпринадлежитM, то и числа 2x+1 и 3x+1 также принадлежат множествуM. Все элементы должны быть различны. Число n вводится.

Исходные данные:

11

Результат:

1 3 4 7 9 10 13 15 19 21 22

1.4.3.3. Отрицательные влево, положительные вправо. В массиве целых чисел переставить элементы так, чтобы все отрицательные числа оказались в начале массива в том же порядке, что в исходном массиве. Аналогично положительные элементы должны оказаться в конце массива, а нули – между отрицательными и положительными. В первой строке задаётся размер массива n, во второй строке – сам массив. Вывести массив-результат.

Исходные данные:

11

2 0 -1 3 0 0 -2 2 -2 3 0

Результат:

-1 -1 -2 0 0 0 0 2 3 2 3

1.4.3.4. В упорядоченном массиве для заданного значения найти номер первого элемента с таким значением, если их несколько. Нумерация с 0. В первой строке задаётся размер массива n, во второй строке – сам массив, в третье – искомое значение.

Исходные данные:

11

-2 -2 -1 0 0 0 2 2 3 3 5

0

Результат:

3

1.4.3.5. В упорядоченном массиве целых чисел для заданного значения найти номер последнего элемента с таким значением, если их несколько. Нумерация с 0. В первой строке задаётся размер массива n, во второй строке – сам массив, в третье – искомое значение.

Исходные данные:

11

-2 -2 -1 0 0 0 2 2 3 3 5

0

Результат:

5

1.4.3.6. Закраска прямой. Интервал прямой с целочисленными координатами [a, b) содержит левую границу – точку a и не содержит правую границу – точку b.

Интервал от 0 до 10⁹выкрасили в белый цвет. Затем было выполнено N операций перекрашивания. При каждой операции цвета в интервале, границы которого задаются, меняются на противоположный (белый на черный, черный на белый). Написать программу, которая найдет самый длинный интервал белого цвета после заданной последовательности операций перекрашивания. В первой строке находится число N (1 <= N <= 500) и затем N строк с границами интервалов (числа в диапазоне от 0 до 10⁹). Вывести одно число – длину самого большого белого интервала.

Исходные данные:

Результат:

1.4.3.7. В массиве целых чисел переставить элементы так, чтобы произведения пар соседних чисел шли в порядке не убывания. В первой строке задаётся размер массива n, во второй строке – элементы массива через пробел.

Исходные данные:

Результат: