/
Author: Дзеранов И.В.
Tags: программирование на эвм компьютерные программы программирование алгоритмы программное обеспечение информационные технологии
ISBN: 978-5-17-169830-0
Year: 2025
Text
Алгоритмы поиска
и сортировки
Иосиф Дзеранов
Ключ к карьере
разработчика
Иосиф Дзеранов
Алгоритмы поиска
и сортировки
Издательство ACT
Москва
УДК 004.421
ББК 32.973-018
Д43
Дзеранов, Иосиф Витальевич.
Д43 Алгоритмы поиска и сортировки / И. Дзеранов. — Москва : Издательство
ACT, 2025.- 144 с.
ISBN 978-5-17-169830-0
Хотите стать хорошим программистом? Начните с алгоритмов! Эффективный код
и решение любых практических задач основываются именно ка них. Эта книга — прак-
тическое руководство по алгоритмам для программистов, готовящихся к собеседованиям
и стремящихся углубить свои знания.
Иосиф Дзеранов -- опытный разработчик, преподаватель и автор ряда популярных
курсов. В этой книге он делится проверенными подходами к решению задач, которые ча-
сто встречаются и реальной работе. Пошаговое изучение алгоритмов поиска и сортировки,
оценки эффективности, а также практические задания делают книгу полезной как для но-
вичков, так и для опытных специалистов.
Издание основано на адаптированием курсе с платформы Stepik.
УДК 004.421
ББК 32,973-018
ISBN 978-5-17-169830-0
© ООО «Издательство АСТ», 2025
Об авторе
Всем привет!
Меня зовут Иосиф Дзера-
нов. Я программист, инженер-
разработчик со стажем более
10 лет. Работал в крупных ком-
паниях (Сбербанк, Mail.ru). Мною
пройден длинный путь от начина-
ющего до старшего разработчика,
и я могу помочь вам добиться та-
кого же успеха.
Коротко про мои достижения:
• Семьянин. Есть двое прекрасных детей;
• Преподаватель и основатель онлайн-школы IRON PROGRAMMER;
• Сертифицированный преподаватель 1Т школы Samsung;
• Четвертьфиналист чемпионата мира по олимпиадному програм-
мированию ACM 1СРС;
• Создатель центра олимпиадной подготовки СОГУ;
• Победит ель VK FELLOWSHIP 2020;
• Победитель в конкурс «Умник» при фонде содействия инновациям;
• Создатель более 55 онлайн курсов по программированию и ин-
форматике.
Связаться со мной можно по почте iodzeranov@maiLru или в Telegram
(t.me/JosefDzeranov).
Telegram: https.//t.me/csharp _ publics
ВКонтакте: https://vk.com/ironprogrammer
Сайт: https://ironprogrammer.ru/
YouTube: https://www.youtube com/@IRONPROGRAMMER
Почта: pro.csharp@mail.ru
Для общения с преподавателем и однокурсниками был соз-
дан данный чат. Здесь можно общаться на любые темы.
Кому адресована эта книга
Эта книга поможет развить навыки алгоритмов, про которые постоянно
спрашивают на собеседованиях при приеме на работу программистов.
Познакомимся с языком алгоритмов, научимся определять эффективность
алгоритма по времени и по памяти.
Затем вас ждет увлекательный мир алгоритмов поиска. Для каждого ал-
горитма разберем его преимущества и недостатки и в каких случаях он
применяется.
Далее мы погрузимся в мир алгоритмов сортировки. Рассмотрим основ-
ные сортировки, отличия между ними, когда и какой алгоритм применять.
Как читать эту книгу
Данная книга является печатной версией онлайн-курса.
Обучающие модули расположены от простого к сложному, что предпола-
гает последовательное и вдумчивое чтение.
Программирование требует практики, поэтому для чтения этой книги по-
надобится компьютер или ноутбук — так вы сможете сразу отрабатывать
теоретические навыки на практических упражнениях.
Книга также может быть использована в качестве справочника для того,
чтобы освежить знания в определенной теме.
H ijflJt ЕЁ] Для тех, кто желает закрепить теорию на практике с автома-
j тической проверкой заданий и обратной связью от препода-
вателя, я оставлю ссылку на онлайн-курс.
ЗШЧАКЙ
Благодарности
Написание книги — это сложный и трудоемкий процесс, который отнял
у меня, а значит, и у моей семьи, большое количество времени и сил,
Я безмерно благодарен своим любимым девочкам — супруге Элизе и доч-
ке Анне — и любимому сыну Лео. Благодаря им у меня есть желание зани-
маться любимым делом, развиваться и становиться лучше.
Отдельно хсчу написать про своего сына Лео! Я до этого представить даже
не мог, что значит иметь сына. Лео, сынок. Если ты когда-нибудь будешь
читать эту' книгу, то знай, что папа тебя очень любит и гордится. Я радуюсь
каждой твоей маленькой победе! Никогда не сомневайся в себе! Ты самый
лучший!
Спасибо моим родителям, которые всегда верили в меня и поддерживали
во всех начинаниях.
Также хочется сказать спасибо всему моему окружению, ведь окружение
во многом определяет, кем мы становимся и куда двигаемся.
И благодарю всех моих учеников, которые мотивировали и вдохновляли
меня выпустить эту книгу.
Спасибо!
Анализ алгоритмов
Асимптотический анализ
Существуют две полярные точки зрения на алгоритмы.
1. Алгоритмы являются основой компьютерных наук. Такой подход
часто встречается.
2. Алгоритмы не нужны.
Я скажу так: важно знать не большое количество алгоритмов, а язык, на
котором обсуждаются алгоритмы.
Алгоритм — это последовательность элементарных действий для выпол-
нения конкретной цели.
Асимптотический анализ 9
Элементарные действия:
1. арифметические опера ции
2. ввод строки, числа
3 вывод строки, числа
4. операторы сравнения
5. операция присваивания
Не элементарные действия:
1. цикл
2. рекурсия
С точки зрения теории алгоритмов, у каждого алгоритма есть входные дан-
ные (input), заложенный алгоритм, который манипулирует входными дан-
ными, и выходные данные, собственно результат манипуляций алгоритма.
В качестве входных данных могут быть число или числа, строки, логиче-
ские значения, комбинация разных типов данных, то есть это та информа-
ция, которая нужна алгоритму, чтобы выполнить поставленную ему задачу.
Выходные данные также могут быть разного вида Вы должны понимать,
что все зависит от конкретной задачи.
Сложность алгоритма?
Сложные алгоритмы?
Простые алгоритмы?
Что такое сложность алгоритма? Алгоритм сложен не для понимания,
а для исполнения. То есть требуется много элементарных операций для
выполнения данного алгоритма, и потому он сложен для машины (ком-
пьютера).
Сложность алгоритма разделяют на две категории:
1. Сложность по времени (временная сложность). Показывает, сколь-
ко времени тратится на выполнение элементарных операций.
2. Сложность по памяти (емкостная сложность). Показывает, сколько
памяти тратится на выполнение элементарных операций.
10 Ана лиз а л гор итмов
Расчет временной сложности
Давайте посчитаем время выполнения следующей программы:
C#
int sum = 0;
for (int i = 0; i < 100; i++)
{
int number = i;
if (number % 3 == 0)
(
sum = sum + number;
}
}
Console.WriteLine(sum);
Даже не представляю из каких соображений будем находить время выпол-
нения данной программы Следовательно, предлагаю замерить с помощью
самой же программы. Для этого воспользуемся классом Stopwatch и по-
считаем количество тиков — минимальная единица измерения времени
выполнения одной операции на процессоре:
C#
Stopwatch stopwatch = new Stopwatch();
s topwatch.Start() ;
int sum = 0;
for (int i = 0; i < 100; i++)
{
int number = i;
if (number % 3 == 0)
{
sum = sum + number;
}
}
Consol e.WriteLine(sum);
Console.WriteLine($"Время выполнения (stopwatch.Elapsed.
Ticks}тиков");
Расчет временной сложности 11
Смотрим результаты:
Время выполнения 96779677 тиков
Время выполнения 96379637 тиков
Время выполнения 1001210012 тиков
Время выполнения 1058110581 тиков
Исходя из результатов замеров можно сказать, что выполнение програм-
мы даже на одном и том же компьютере дает разное время выполнения.
Что уж говорить про запуск программы на разных компьютерах с разными
характеристиками.
Можно задаться вопросом, почему нельзя однозначно определить время
работы алгоритма на компьютере? Потому что программы запускаются
в операционной системе (в моем случае Windows), которая устроена не гак
просто, как кажется обычному пользователю компьютера:
• некоторые элементарные операции могут выполняться процессо-
ром дольше, чем другие Зсе зависит от того, в какой момент была
запушена программа;
• в многозадачных операционных системах выполнение алгоритма
может приостанавливаться на время выполнения других важных
для ОС задач. Это решается на уровне операционной системы;
• кэш процессора может ускорять работу с памятью, однако алго-
ритмы не могут напрямую управлять работой кэша;
• компиляция одной и той же программы разными комп и л яторами или
с разными настройками компилятора может давать разный набор
элементарных машинных инструкций. Например, компиляция под
debug и release версии дают разный набор машинных инструкций.
Вывод, определить точное время выполнения в тиках или в миллисе
кундах практически невозможно.
Перечислим, что может влиять на время выполнения программы:
1. количество ядер на компьютере;
2. скорость чтения/записи в память;
3. 32- или 64-разрядная операционная система;
12 Анализ алгоритмов
4. кэш процессора;
5. файлы подкачки;
6. входные данные.
В realtime системах, например, таких
как биржи, управление самолетом,
важны наносекунды, так как время,
в течение которого информация ак-
туальна, крайне мало. То есть, если
мы получили значения датчиков са-
молета и слишком долго анализи-
ровали и считали, то выходное воз-
действие может быть неактуальным.
Из -за этого н системах, где критично
важно время выполнения програм-
мы, считают каждую операцию в ти-
ках. В таких системах важно, на ка-
ком компьютере данная программа
выполняется, так как учитывается
все окружение.
В среднем по характеристикам современном персональном компьютере
за 1 секунду выполняется примерно миллиард элементарных операций.
Теория алгоритмов
В теории алгоритмов не рассматривают характеристики окружения, на
котором выполняется программа. Учитывают только входные данные! От
них будет зависеть количество элементарных действий. Важна тенденция
на большом количестве входных данных.
Запомни: при анализе алгоритма следует понимать, как меняется ко-
личество действий при увеличении количества входных данных.
Почему нам важно для больших входных данных? А все потому, что на ма-
леньких данных большинство алгоритмов работают достаточно быстро,
а вот с увеличением входных данных уже нужно смотреть и англизировать.
Все в этом мире растет и приумножается: машины, железные дороги, кни-
ги, поэтому мы и исследуем то, насколько наш алгоритм сможет «выдер-
Теория алгоритмов 13
жать» потенциальный рост данных. «Выдержать» значит уложиться в огра-
ничения по времени и по памяти из условий задачи.
На самом деле расчет временной сложности можно рассматривать как не-
которую функцию, которая принимает входные данные и выдает количе-
ство элементарных операций, потраченных на обработку этих данных.
Рассмотрим следующую программу:
C#
static void Sum(int a, int b)
(
int sum = a + b;
Console.WriteLine(sum);
)
Посчитаем, сколько здесь элементарных действий. В данной программе
три элементарных действия, сложение, присваивание и вывод на консоль.
Говорят, что данная программа занимает константное время, так как от
увеличения входных данных а и b количество элементарных действий не
поменяется. И обозначают как 0(1) — говорят: о большое от единицы. По-
чему от единицы? Потому что как бы мы не увеличивали входные данные,
количество действий не изменится. Эти действия ничтожно малы и равны
единице по сравнению с входными данными.
14 Анализ алгоритмов
Рассмотрим программу и посчитаем для алгоритма временную сложность:
Сй
static void Print(int n)
{
for (int i - 1; i <= n; i++)
{
Console.WriteLine(i);
}
}
При n=5 алгоритм сделает 5 действий вывода на экран. Если мы п увеличим
в 10 раз, то количество действий также увеличится не более чем в 10 раз.
Так вот, сложность алгоритма называется линейной, если при увеличении
входных данных в п раз, количество элементарных действий алгоритма уве-
личится не более чем в п раз. Говорят, что алгоритм имеет линейную слож-
ность, либо алгоритм работает за линию. Еще говорят, что алгоритм делает
нс более чем п операций, и записывают как О(п) — говорят: О большое от п.
Давайте все-таки считать точнее количество элементарных операций
или действий:
Задача 1.
• 1 операция для int i = 1
• n+1 операций сравнения при i <= п
• 2п операций для i++ (эквивалентно i = i + 1, а это две операции:
присваивание и сложение)
• и операций для Console,WriteLine(i)
Итого: временная сложность равна 0(1 + (п + 1) + 2п + л) = О(4л + 2).
Теория алгоритмов 15
Задача 2.
• 1 операция для int i = О
• 1 операция для int count = О
• п+1 операций сравнения при i < п
• 2п операций для i++
• nn итераций цикла for и каждый раз:
о 1 операция для int j = О
о п+1 операций сравнения при J < п
о 2 п операций для j++
о 2п операций для count++
Итого: временная сложность равна 0(1 + 1 + (п + 1) + 2n + n(l + (n + 1) +
2п + 2п)) = О(5п1 2 + 5п + 3).
Согласитесь, что даже для простых алгоритмов сложно посчитать точное ко-
личество элементарных операций. Из-за этого ввели такое понятие как асим-
птотическая сложность, с помощью которого вычисляется сложность алгорит
мов. Если говорить по-простому, то она получается следующим образом:
1. отбросим в функции сложности все слагаемые, кроме одного с са-
мой быстрой скоростью роста;
2. отбросим все ко нстан гы.
Это и будет асимптотической оценкой сложности.
Зная теперь, что такое асимптотическая сложность, давайте посчитаем для
примеров, которые были приведены выше:
16 Анализ алгоритмов
1. Для первой задачи временная сложность равна О(4п+2). Оставим
только слагаемое 4п, так как оно является с самой быстрой скоро-
стью роста. Л потом уберем константу 4, так как при увеличении
в, константа 4 большой роли не играет. То есть, асимптотическая
сложность будет равна О(п).
2. Для второй задачи временная сложность равна 0(5 п2 + 5л + 3).
Оставим только слагаемое 5п2, так как оно является с самой бы-
строй скоростью роста. А потом уберем константу 5, так как при
увеличении п константа 5 большой роли не играет То есть асим-
птогическая сложность будет равна О(п2).
Давайте посмотрим на часто используемые и встречающиеся асимптоти-
ческие сложности:
Оценки сложности расположены в возрастающем порядке по асимптоти-
ческой сложности. Чем выше его оценка, чем сложнее данный алгоритм,
то есть алгоритм делает в разы больше операций при кратном увеличении
входных данных.
Полезно иметь оценку' сложности того или иного алгоритма, но еще важнее
то, что с помощью таких оценок можно сравнивать друг с другом разные
алгоритмы для решения одной задачи. Допустим, для некоторой задачи име-
ется два алгоритма, трудоемкость одного из них оценивается как 2п2, а дру-
гого — как 1 ООп. Тогда при небольшой длине входа (п <50) предпочтительнее
использовать первый алгоритм, а при большой (п >50)—второй. Но при ма-
лой длине входа время работы каждого из двух алгоритмов будет невелико,
Расчет временной сложности на практике 17
так что,, может быть, мы практически ничего не потеряем, если и здесь будем
пользоваться вторым алгоритмом. Этот пример помогает понять, почему при
анализе сложности алгоритмов главное внимание уделяется асимптотиче-
скому поведению сложности, то есть поведению при больших длинах входа.
Расчет временной сложности на практике
Задание 1.
с#
int n = Convert.Tolnt32(Console.ReadLine());
int a = n / 100;
int b = n / 10% 10;
int c = n % 10;
int revert = c * 100+b* 10+ a;
Console.WriteLine(revert);
Решение:
Заметим, что при увеличении входного параметра п количество операций
не поменяется. А количество операций будет конечное количество, следо-
вательно асимптотическая сложность 0(1).
Ответ: 0(1).
Задание 2.
с#
int n = Convert.ToTnt32(Console.ReadLine());
int count = 0;
for (int i = 0; i < n; i++)
{
int number = Convert. Tolnt32 (Console.
ReadLine());
if (number % 10 == 0)
{
count = count + 1;
}
}
Console.WriteLine(count);
18 Анализ алгоритмов
Решение:
Заметим, что количество операций зависит от п. А точнее, если мы п уве-
личим в 10 раз, то количество операций увеличится не более чем в 10 раз.
Следовательно, асимптотическая сложность линейная, то есть О(п).
Ответ; О(п).
Задание 3.
Определите асимптотическое время работы алгоритма
C#
int n = Convert.Tolnt32(ConsoJе.ReadLine());
int count = 0;
int i = 1;
while (i <= n * n)
{
ccunt++;
i = i * 3 ;
}
Console. WriteLine(count);
Решение:
Заметим, что сложность нашего алгоритма будет О(1од3п* i 2).
Давайте всг.омним свойства логарифмов:
1. При смене основания добавляется константный множитель:
1одп=С1одьп,
2 Степень аргумента логарифма можно перекинуть в множитель
перед логарифмом: log п2 - 2 log п.
По свойству 1, логарифм можно привести к любому основанию. Поэтому
под символом О основание у логарифма опускают. Точно так же, как опу-
скают константные множители. То есть OUogg2) ~ О(1од л2).
По свойству 2, степень аргумента логарифма вынесем перед логарифмом
в виде множителя, то есть Ofjogn2) = О(21одп). При увеличении л константа
2 не играет большой роли, следовательно, можем его опустить и получить
окончательный вид асимптотической сложности О(21одп) - О(21одп).
Ответ: О(1о д л)
Расчет сложности по памяти 19
Расчет сложности по памяти
Сложность по памяти — это показатель эффективности вашего кода с точ-
ки зрения используемой памяти. Анализ сложности по памяти происходит
так же, как анализ временной сложности, только вместо количества опера-
ций смотрим на используемую программой память.
Например, рассмотрим следующий код:
C#
int n = Convert.Tolnt32(Console.ReadLine());
int[] array ₽ new int[n];
for (int 1=0; i < n; i++)
{
array[i] = i * 2;
}
Фрагмент кода создает массив размера п. Таким образом, сложность кода
по памяти равна О(п),
Память измеряется с точки зрения наибольшего использования памяти
программой при ее запуске. То есть, если вы выделили О(п) памяти, а за-
тем освободили ее, это НЕ сделает сложность по памяти вашей программы
0(1).
Задание 1.
Определите асимптотическую сложность по памяти алгоритма
C#
int n = Convert.Tolnt32(Console.ReadLine());
int sum = 0;
for (int i = n * n; i > 1; i—)
{
n = Convert.Tolnt32(Console.ReadLine());
sum += n;
}
Console .WriteLine(sum);
20 Анализ алгоритмов
Решение:
Дан цикл, который имеет п2 итераций. То есть временная сложность равна
О(п2). Flo память затрачивается только на две переменные, следовательно,
сложность по памяти равна 0(1).
Выводы
• Опытные инженеры и программисты анализируют алгоритмы еже-
дневно, не задумываясь, на уровне рефлексов. Делают они это для
предварительного грубого анализа кода, который читают, пишут
или только собираются написать.
• Предсказать, как быстро будет выполняться хоть немного нетри-
виальный алгоритм, — крайне трудная задача, поэтому, если вам
нужна максимальная производительность, помогут только кро
потливые эксперименты и замеры производительности. Если вы
пишете на С#, то для замера производительности посмотрите та-
кую библиотеку, как BenchmarkDotNet (https://githuh.ccm/dotnet/
BenchmarkDotNet).
• Для большинства ситуаций пиковая производительность не осо-
бенно важна. Тогда быстрого анализа асимптотики алгоритма до-
статочно, чтобы исключить случайное появление сильно неэффек-
тивного кода.
• Вы должны понимать, что одна асимптотика для одной задачи мо-
жет быть приемлемой, а для второй задачи кет. Следовательно,
нельзя точно определить границу эффективности асимптотики ал-
горитма. Для каждой конкретной задачи эта граница своя.
Алгоритмы поиска
Общая информация о поиске
Одним из важнейших действий со структурированной информацией явля-
ется поиск. Поиск — процесс нахождения конкретной информации в мно-
жестве данных.
Пусть есть таблица учеников школы IRON PROGRAMMER (все имена вы-
думанные):
ФИО Предмет Возраст
Иванов Иван Иванович Подготовка к ЕГЭ 30
Петров Петр Петрович Основы программирования 20
Попов Николай Федорович Алгоритмы поиска и сортировки 19
Соколов Сергей Витальевич Основы программирования 21
Сергеев Сергей Сергеевич Оконные приложения 25
Васильев Василий Васильевич Алгоритмы поиска и сортировки 27
И пусть нужно найти всех учеников, которые занимаются по предмету «Ос-
новы программирования». Это типичная практическая задача на поиск.
Что из себя представляют данные? Данные представляют собой записи
(строки) об учениках с информацией о ФИС, предмете и возрасте Дан-
ные представляют собой сложную структуру (содержат много разной ин-
формации). Следовательно, нам нужно выделить свойство или несколько
свойств, по которым будем выполнять поиск. В рассматриваемой задаче
этим свойством будет «Предмет».
22 Алгоритмы поиска
Свойство записи, по значению которого происходит поиск, называется
ключом поиска.
Целью поиска является нахождение всех записей (если они есть) с данным
значением ключа.
На курсе НЕ будут использоваться сложные записи. Для простоты будем
брать числа. Но вы должны понимать, что в реальной практической задаче
каждое число может быть свойством сложного объекта, которое является
ключом.
Например: дана последовательность целых чисел [3,5,6,3,1,5,51]. Нужно
найти все числа со значением 3.
В данном случае, целью поиска является нахождение всех чисел (если они
есть) с конкретным целочисленным значением 3.
Поиск является одним из наиболее часто встречаемых действий в про-
граммировании. Существует множество различных алгоритмов поиска,
которые принципиально зависят от способа организации данных. У каж-
дого алгоритма поиска есть свои преимущества и недостатки. Поэтому
важно выбрать тот алгоритм, который лучше всего подходит для решения
конкретной задачи.
Линейный поиск 23
Линейный поиск
Проблема
Есть множество целых чисел. Нужно определить, встречается ли в нем
конкретное число х. Если есть такое число в множестве, то вывести YES,
в противном случае — NO.
Входные данные Выходные данные
5 6 12 65 52 11 65 VES
5 6 12 65 52 11 10 NC
Идея решения
Множество элементов просматривается последовательно в некотором
порядке, гарантирующем, что буд^с просмотрены все элементы множе-
ства (например, слева направо). Если в ходе просмотра множества будет
найден искомый элемент, просмотр прекращается с положительным ре-
зультатом. Если же будет просмотрено все множество, а элемент не будет
найден, то искомый элемент не найден.
Суть алгоритма линейного поиска
Линейный поиск — это простейший вид поиска заданного элемента на не-
котором множестве, осуществляемый путем последовательного сравне-
ния очередного рассматриваемого значения с искомым до тех пор, пока
эти значения не совпадут.
24 Алгоритмы поиска
Линейный поиск 25
Алгоритм
Пройдемся по данному множеству чисел. Каждое число будем сравнивать
с искомым числом х. Если встретили равное ему число, то прекращаем
дальнейший просмотр и возвращаем положительный результат. Если рас-
смотрели все числа множества, возвращаем отрицательный результат.
Реализация
с#
static bool LinearSearch (int [ ] array, int key)
{
for (int i = C; i < array.Length; i++) // преходимся
по массиву
{
if (array[i] == key) // если текущий элемент равен
ключу
{
return true; // нашли нужный элемент
}
}
return false; // не нашли нужный элемент
}
Время работы
Временная сложность Время работы Комментарий
Лучшее 0(1) В лучшем случае, когда искомый элемент за- нимает первую позицию, алгоритм произведет всего одно сравнение
Среднее В среднем этот алгоритм требует п/2 итераций цикла
Худшее 0(п) Худшему случаю соответствуют две ситуации: искомый элемент занимает последнюю пози- цию или он вовсе отсутствует в массиве
Примечание: за и обозначили количество элементов в последовательно-
сти.
26 Алгоритмы поиска
Преимущества и недостатки
Преимущества Недостатки
Прост в реализации В худшем случае осуществля- ется просмотр всего множества
Не требует сортировки значений множества Используется, если множество содержи7 небольшое количе- ство элементов
Не требует дополнительной памяти
Может работать в потоковом режиме при не- посредственном получении данных из любо- го источника
Применимость
Алгоритм линейного поиска часто исполь-
зуется на практике. Его применение оправ-
данно на небольших и/или неотсортиро-
ванных последовательностях, либо в слу-
чае одиночного поиска в неупорядоченном
списке.
Когда последовательность состоит из боль-
шого числа элементов и с ней предстоит
работать не раз, тогда наиболее оптималь-
ным решением оказывается предваритель-
ная сортировка этой последовательности
с последующим применением двоичного
(рассмотрим позже) или другого, отлично-
го ст линейного, алгоритма поиска.
Задачи 27
Задачи
Поиск
Напишите программу, которая определяет, сколько раз встречается задан-
ное число х в данном массиве.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
1000.
Во второй строке вводятся N целых чисел, каждое из которых по модулю
не превосходит 1000.
В третьей строке содержится одно целое число х, не превосходящее по
модулю 1000.
Выходные данные
Вывести одно число — количество чисел, равных х.
Sample Input 1:
6
6 8 5 1 5 4
5
Sample Output 1:
2
Sample Input 2:
3
1 2
5
Sample Output 2:
0
28 Алгоритмы поиска
Поиск-2
Напишите программу, которая определяет, встречается ли заданное число
х в последовательности чисел.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
1000.
Во второй строке вводятся /V целых чисел, каждое из которых по модулю
не превосходит 1000.
В третьей строке содержится одно целое число х, не превосходящее по
модулю 1000.
Выходные данные
Вывести YES, если число х встречается в данном массиве, и NO в против-
ном случае.
Sample Input 1:
6
1 2 3 4 5 6
5
Sample Output 1:
YES
Sample Input 2:
3
2 3 10
5
Sample Output 2:
NO
Задачи 29
Поиск-3
Напишите программу, которая выводит номера элементов последователь-
ности, равных данному числу.
Входные данные
В первой строке задается одно натуральное число /V, не превосходящее
1OGG
Во второй строке вводятся Л/ целых чисел, каждое из которых по модулю
не превосходит 1000.
Б третьей строке содержится одно целое число х, не превосходящее по
модулю 1000.
Выходные данные
Вывести номера элементов, равных данному, в порядке возрастания. Если
таких элементов нет, ничего выводить не нужно.
Sample Input 1:
5
23 4 56 8 2
4
Sample Output 1:
2
Sample Input 2:
5
23 4 56 4 2
4
Sample Output 2:
2 4
Sample Input 3:
5
30 Алгоритмы поиска
1 2 3 4 5
3
Sample Output 3:
3
Ближайшее число
Напишите программу, которая находит в последовательности элемент, са-
мый близкий по величине к данному числу.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
1000.
Во второй строке содержатся N целых чисел, каждое из которых по мо-
дулю не превосходит 1000.
В третьей строке вводится одно целое число х, по модулю не превосходя
1цее 1000.
Выходные данные
Вывести значение самого ближайшего элемента к х. Если таких чисел не-
сколько, вывести наибольшее из них.
Sample Input 1:
3
2 10 5
6
Sample Output 1:
5
Sample Input 2:
3
2 10 5
1
Задачи 31
Sample Output 2:
2
Sample Input 3:
3
2 10 5
8
Sample Output 3:
10
Хитрюга
Школьник Витя получил доступ к онлайн журналу на ДНЕВНИК.РУ и хочет
заменить все свои минимальные оценки на максимальные. Помогите Вите
написать программу, которая заменит его минимальные оценки на макси-
мальные.
Входные данные
На первой строке вводится одно натуральное число /V — количество оце-
нок Вити, которое не превышает 1000.
На второй строке через пробел вводятся оценки Вити — натуральные числа
от 2 до 5.
32 Алгоритмы поиска
Выходные данные
Требуется вывести исправленные оценки в том же порядке.
Sample Input 1:
3
4 5 5
Sample Output 1:
5 5 5
Sample Input 2:
5
2 2 2 3 4
Sample Output 2:
4 4 4 3 4
Sample Input 3:
1
5
Sample Output 3:
5
Первый номер
Напишите программу, которая выводит номер элемента последователь-
ности, равного данному числу. Если таких элементов несколько, выведите
номер первого из них.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
1000.
Во второй строке вводятся N целых чисел, каждое из которых по модулю
не превосходит 10ОО.
Задачи 33
В третьей строке содержится одно целое число х, не превосходящее по
модулю 1000.
Выходные данные
Вывести номер элемента, равного данному числу. Если таких элементов
несколько, выведите номер первого из них.
Если таких элементов нет, ничего выводить не нужно.
Sample Input 1:
5
23 4 56 8 2
4
Sample Output 1:
2
Sample Input 2:
5
23 4 56 8 4
4
Sample Output 2:
2
Sample Input 3:
5
23 1 56 8 2
4
Sample Output 3:
34 Алгоритмы поиска
Последний номер
Напишите программу, которая выводит номер элемента последователь-
ности, равного данному числу. Если таких элементов несколько, выведите
номер последнего из них.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
1000.
Во второй строке вводятся N целых чисел, каждое из которых по модулю
не превосходит 1000.
В третьей строке содержится одно целое число х, не превосходящее по
модулю 1000.
Выходные данные
Вывести номер элемента, равного данному числу. Если таких элементов
несколько, выведите номер последнего из них.
Если таких элементов нет, ничего выводить не нужно.
Sample Input 1:
5
23 4 56 8 2
4
Sample Output 1:
2
Sample Input 2:
5
23 4 56 8 4
4
Sample Output 2:
5
Бинарный поиск 35
Sample Input 3:
5
23 1 56 8 2
4
Sample Output 3:
Бинарный поиск
Проблема
Дана последовательность упорядоченных чисел, состоящая не более чем
из 2 • 109 элементов. Надо найти индекс элемента данной последовательно
сти, который равен числу х. Если искомого числа нет в последовательно-
сти, необходимо вывести -1. Также в задаче есть ограничение по времени
500 ms, то есть половина секунды.
Сначала вводится количество элементов в последовательности. Затем
сама последовательность. А потом искомый элемент. Изучите примеры
входных и выходных данных для полного понимания задачи:
Входные данные Выходные данные
7 -10-5 4 6 8 10 11 10 5
5 -2 10100 250315 -2 0
5 -2 1С100 250315 15 -1
36 Алгоритмы поиска
Идея алгоритма бинарного (двоичного) поиска
(Binary search)
Заметим, что если применим линейный поиск, то алгоритм будет рабо-
тать в худшем случае за О(п) = 0(109) А как мы знаем, это больше секун-
ды. То есть мы здесь уже не можем использовать линейный поиск. Для
ускорения времени работы программы нам поможет алгоритм бинарного
поиска.
Так как массив отсортирован (это ОЧЕНЬ важно), мы можем проверить,
есть ли в нем какое-то конкретное значение, методом деления пополам.
Возьмем элемент, находящийся в середине массива, и сравним с искомым,
то есть с х. Если он больше искомого, то отбросим вторую половину масси
ва — там его точно нет, так как если искомый элемент меньше серединного
элемента, то он заведомо меньше всех элементов, находящихся после него
(из-за упорядоченных чисел). Если же меньше, то наоборот — отбросим
начальную половину. И так будем продолжать делить пополам, пока не
найдем нужный элемент.
Суть алгоритма бинарного поиска
Бинарный поиск (Binary search) — это поиск заданного элемента на уно
рядоченном множестве, осуществляемый путем неоднократного деления
этого множества на две части таким образом, что искомый элемент попа-
дает в одну из этих частей. Поиск заканчивается при совпадении искомого
элемента с элементом, который является границей между частями множе-
ства, или при отсутствии искомого элемента.
Бинарный поиск применяется к отсортированным множествам.
Алгоритм
1. Зона поиска (на первом шаге ей является весь массив) делится на
две равные части путем определения ее среднего (mid) элемента;
2 Средний элемент сравнивается с искомым (х), результатом этого
сравнения будет один из трех случаев:
о х < mid. Крайней правой границей области поиска становится
элемент, стоящий перед средним (right *- mid -1);
Бинарный поиск 37
о х > mid. Крайней левой границей области поиска становится
следующий за средним элемент (left *- mid + 1);
о х = mid. Значения среднего и искомого элементов совпадают,
следовательно, элемент найден, работа алгоритма завершается.
3. Если для проверки не осталось ни одного элемента, то алгоритм
завершается, иначе выполняется переход к пункту 1.
Отладка
В таблице ниже представлен конкретный целочисленный массив и поша-
говое выполнение алгоритма бинарного поиска применительно к его эле-
ментам:
iиндекса- ция номер итерации 0 1 2 3 4 5 6 7 8 left, гчmid
1 1 4 9 16 25 36 49 64 left = 0 right = 8 mid = 4
2 1 4 9 25 36 49 64 81 left = 0 right = 3 mid = 1
3 1 4 9 25 36 49 64 81 left = 2 right = 3 mid = 2
4 1 4 9 16 25 36 49 64 81 left = 3 right = 3 mid - 3
Имеется последовательность целых чисел, расположенных в порядке воз-
растания (1 4 9 16 25 36 49 64 81), а также ключ — число 16. Изначально
граничными элементами являются элементы с индексами 0 и 8 и значе-
ниями 1 и 81. Вычисляется индекс среднего элемента с помощью форму-
лы. После сравнения оказывается, что искомый элемент меньше среднего,
и поэтому последующий поиск осуществляется в левой части последова-
тельности. Алгоритм продолжает выполняться подобным образом до на-
хождения на 4 шаге искомого элемента.
Реализация
При вычислении индекса среднего элемента могут быть проблемы с пере-
полнением целочисленного типа данных (int). Например, пусть есть мас-
сив, состоящий из 2 •10*’ элементов, и искомый элемент находится ближе
к концу массива. На одном бы из шагов получилось, что left-1999999997,
38 Алгоритмы поиска
a right = 2 109. Тогда при вычислении середины произойдет переполне-
ние целочисленной переменной, то есть результатом такой операции бу-
дет число «-147483649». Стоит сказать, что переполнения не произойдет
в Python, так как тэм встроена длинная арифметика.
Чтобы переполнения не происходило, давайте вспомним нашу люби-
мую математику. Перепишем нашу формулу чуть по-другому, применяя
школьные знания по математике. Данная формула эквивалентна следую-
щей формуле:
, right - left 2 • left + right - left
lef 11----~------=----------j--------= left ¥ right!
Ci L
r, . , . right-left „ -
В формуле left + 2-----переполнении уже не будет, следовательно,
при вычислении индекса серединного элемента используем именно ее.
C#
static int Binarysearch(int[] array, int x)
{
int left = 0;
int right = array.Length — 1;
while (left <= right)
{
int m = left + (right — left) / 2; // вычисление
серединного элемента
if (array[m] == x) // если серединный элемент равен
ключу, то вернем индекс серединного элемента
return m;
if (array [in] < x) // если серединный элемент меньше
ключа, то смещаем левую границу
left = m + 1;
else
right = m — 1; // если серединный элемент больше
ключа, то смещаем правую границу
}
return -1; // если не нашли соответствующего элемента,
возвращаем «-1»
}
Бинарный поиск 39
Время работы
Для анализа алгоритма бинарного поиска нам необходимо вспом-
нить, что каждое сравнение исключает из рассмотрения около по-
ловины оставшихся элементов. Каково максимальное число срав-
нений, которые потребует алгоритм для проверки списка целиком?
Если мы начинаем с п элементов, то после первого сравнения отбросится
около п/2 элементов.
После второго — порядка п/4. Потом п/8, п/16 и так далее. Сколько раз мы
будем разделять список? Таблица поможет найти ответ.
Табличный анализ для бинарного поиска
Сравнения Приблизительное количество отброшенных элементов
1 п/2
2 п/4
3 п/8
i
Процесс разбиения закончится на списке, содержащем всего один эле-
мент. Им может оказаться или не оказаться то, что мы ищем. В любом
случае дело сделано. Количество сравнений, необходимых до попадания
в эту* точку, равно i, где =1. Решив уравнение для i, получаем / = 1од2п =
log п. Максимальное количество сравнений является логарифмом по отно-
шению к количеству элементов в списке. Таким образом, бинарный поиск
будет 0(1од п).
Логарифм — ужасно медленно растущая функция. Если вы не знаете, на-
сколько эффективен бинарный поиск, попробуйте поискать имя в теле-
фонной книге, содержащей миллион имен. Бинарный поиск позволяет си
стематически находить любое имя, используя не более 20 сравнений, так
как 2го = 1048576 > 106. Если бы вы могли управлять списком, содержащим
всех людей в мире, отсортированных по имени, вы могли бы найти любого
человека менее чем за 35 шагов. Это может показаться нереальным, но
это действительно так.
40 Алгоритмы поиска
Рассмотрим массив с записями Googol. Это намного больше предметов,
чем количество частиц в наблюдаемой вселенной.
Бинарный поиск может найти элемент в этом массиве не более чем за 333
шага, в то время как линейный поиск займет больше времени, чем жизнь
Вселенной.
Что такое Googol?
А сколько частиц во вселенной?
Временная сложность Время работы Комментарий
В лучшем 0(1) В лучшем случае, когда искомый элемент находится в середине массива, алгоритм произведет всего одно сравнение
В среднем O(Jogn) В среднем этот алгоритм требует log п итераций цикла
В худшем 0(1од л) Худшему случаю соответствуют две ситуации: искомый элемент находится в последней итерации цикла или он вовсе отсутствует в массиве
Бинарный поиск 41
Преимущества и недостатки
Преимущества Недостатки
Быстрота выполнения поиска Сложен в реализации
Используется, если множество содержит большое количество элементов Применяется только на упорядоченном множестве
Не требует дополнит ельной памяти Не может работать в потоковом режиме при непосредственном по лучении данных из любого источника
Применимость
Применяется на упорядоченном массиве с большим количеством элемен-
тов при ограниченном времени выполнения.
Распространенные ошибки:
• не работает с массивом из 0/1 /2 элементов;
• не находит первый или последний элемент;
• некорректно работает, если элемента в массиве нет;
• некорректно работает, если в массиве есть повторяющиеся эле-
менты;
• обращение к элементам за пределами массива;
• козырная, которая была в языке Java — переполнение целого при
вычислении среднего индекса.
Реальные примеры использования
Автозаполнение
Рассмотрим следующую проблему: вы создаете браузер и хотите предо-
ставить автозаполнение, когда пользователь вводит L'RL-адрес страницы.
Пользователь можег потенциально иметь тысячи URL-адресов в своей
истории поиска, поэтому линейный поиск по ним для автозаполнения че-
рез некоторое время просто перестанет его устраивать.
42 Алгоритмы поиска
Задачи
Игра
Некто загадал число от 1 до N. За какое наименьшее количество вопросов
(на которые он отвечает «да» или «нет») можно угадать задуманное числе?
Формат входных данных
Вводится одно натуральное число N, которое не превышает 10 ООО.
Формат выходных данных
выведите наименьшее количество вопросов, которого гарантированно
хватит, чтобы угадать задуманное число.
Sample Input 1:
8
Sample Output 1:
3
Sample Input 2:
10
Бинарный поиск 43
Sample Output 2:
4
Sample Input 3;
2.
Sample Output 3:
1
Sample Input 4:
3
Sample Output 4:
2
Бинарный поиск
Реализуйте алгоритм бинарного поиска.
Входные данные
В первой строке входных данных содержатся натуральные числа N и К
100000).
Во второй строке задаются Л' элементов первого массива, отсортирован-
ного по возрастанию
I- третьей строке — К элементов второго массива.
Элементы обоих массивов — целые числа, каждое из которых по модулю
не превосходит 109.
Выходные данные
Требуется для каждого из К чисел вызести в отдельную строку YES, если
это число встречается в первом массиве, и NO в противном случае.
44 Алгоритмы поиска
Sample Input 1:
10 5
123456789 10
2 0 4 9 12
Sample Output 1:
NO
NO
YES
YES
NO
Sample Input 2:
10 10
1 61 126 217 28766127 391 62 98126712687 1000000000
1006127 1 61200-10000 1217 100001000000000
Sample Output 2:
NO
YES
YES
YES
NO
NO
YES
YES
NO
YES
Sample Input 3:
10 10
-8--6 -4- 4 -2-1 0 2 3 3
8 3-3 -2 2-1 2 9--8 0
Sample Output 3:
NO
YES
NO
Модификации бинарного поиска 45
YES
YES
YFS
YES
NO
YES
YES
Модификации бинарного поиска
В массизе может встречаться несколько элементов со значениями, рав-
ными искомому элементу. Рассмотренный ранее алгоритм находит пер-
вый совпавший с искомым элемент который в порядке следования в мас-
сиве может быть ни первым, ни последним среди равных искомому эле-
менту'. Например, в массиве чисел [1,5,5,5,5,5,5,7,8] искомый элемент х-5
совпадет с элементом с индексом 4, который не относится ни к первому, ни
к последнему элементу, равному искомому.
Существуют две модификации рассматриваемого алгоритма для поиска
первого и последнего вхождения искомого элемента. Вее зависит от того,
какой инвариант мы выберем.
46 Алгоритмы поиска
Нахождение самого левого вхождения
Идея
При равенстве серединного элемента с искомым элементом будем сме-
щать правую границу к середине. То есть, если одинаковые элементы бу-
дут находиться рядом, то мы постоянно будем смещать правую границу, то
есть двигаться в левую сторону. Индекс элемента, который равен искомо-
му, будет находится в right.
Одним из важных моментов: значение left должно выходить за границы
массива слева (равняться -1), чтобы right смог принять всевозможные зна-
чения, в том числе и 0. Всегда во время выполнения алгоритма сохраняет
ся инвариант (left, right], то есть левая граница НЕ включается, а правая
включается. Таким образом, мы найдем в right самое левое вхождение
искомого элемента. Давайте посмотрим наглядно, как будет работать ал-
горитм:
i индек- сация номер итерации -1 0 1 2 3 4 5 6 7 8 left, right.
1 1 5 5 5 5 5 7 8 left = -1 right = 8 mid = 3
2 1 5 5 5 5 5 7 8 left = -1 right = 3 mid = 1
3 1 5 5 5 5 5 5 7 8 left = -1 right = 1 mid = 0
4 1 5 5 5 5 5 5 7 8 left = 0 right = 1 mid = 0
Выйдем после того, как left = 1, a right = 1. Проверяем, равен ли элемент
с индексом right = 1 искомому элементу. Если равен, то возвращаем right,
иначе возвращаем «-1».
Модификации бинарного поиска 47
Реализация
си
static int LeftBinarySearoh(int[] array, int x)
(
int left = -1; // исключаем из возможных значений
ответа
int right = array.Length — 1; // ответ будет
находиться здесь
while (left + 1 < right)
{
int m = left + (right — left) / 2; // вычисление
серединного элемента
if (array[m] < x) // если серединный элемент
меньше искомого, то смещаем левую границу
left = ш;
else
right = m; II если серединный элемент больше
либо равен искомому, то смещаем правую границу
}
if (array[right] == х) // проверка, что действительно
в этом месте нужный элемент
return right;
return -1; // если не нашли соответствующий элемент,
возвращаем «-1»
}
Нахождение самого правого вхождения
Идея
При равенстве серединного элемента с искомым будем смещать левую
границу к середине. То есть, если одинаковые элементы будут находиться
рядом, го мы постоянно будем смещать левую границу, то есть двигаться
в правую сторону. Индекс элемента, который равен искомому элементу,
будет находится в left.
Важный момент: значение right должно выходить за границы массива
справа (равняться длине массива л), чтобы left смог принять всевозмож-
ные значения, в том числе и л - 1. Всегда во время выполнения алгорит-
ма сохраняется инвариант [left, right), то есть левая граница включается,
а правая НЕ включается. Таким образом, мы найдем в left самое правое
48 Алгоритмы поиска
вхождение искомого элемента. Давайте посмотрим наглядно, как будет
работать алгоритм:
i индексация номер ите- рации 0 1 2 3 4 5 6 7 8 9 left, right, mid
1 1 5 5 5 5 5 5 7 8 left = 0 right = 9 mid = 4
2 1 5 5 5 5 5 5 7 8 left = 4 right = 9 mid = 6
3 1 5 5 5 5 5 5 8 left = b right = 9 mid = 7
4 1 5 5 5 5 5 5 7 8 left = 6 right = 7 mid = 6
Выйдем после того, как left = 6, a right = 7. Проверяем, равен ли элемент
с индексом left = 6 искомому элементу. Если равен, то возвращаем left,
иначе возвращаем «-1».
Модификации бинарного поиска 49
Реализация
с#
static int RightBinarySearch(intI] array, int x)
{
int left =0; // ответ будет находиться здесь
int right = array.Length; // исключаем из возможных
значений ответа
while (left + 1 < right)
{
int m = left + (right - left) /2; // вычисление
серединного элемента
if (array[m] <= x) // если серединный элемент
меньше либо равен искомому, то смещаем левую границу
left = ш;
else
right = m; // если серединный элемент больше
искомого, то смещаем правую границу
}
if (array[left] == х) // пронерка, что действительно
в этом месте нужный элемент
return left;
return -1; // если не кашли соответствующий элемент,
возвращаем «-1»
}
Задачи
Левый двоичным поиск
Дано два списка чисел, числа в первом списке упорядочены по неубыва-
нию. Для каждого числа из второго списка определите номер первого по-
явления этого числа в первом списке.
Входные данные
В первой строке входных данных записано два числа /V и М (1CN, МС20000).
Во второй строке записано W упорядоченных по неубыванию целых чи-
сел — элементы первого списка. Все элементы массива по модулю не пре-
восходят 1 О’.
50 Алгоритмы поиска
В третьей строке записаны М целых неотрицательных чисел — элементы
второго списка. Все элементы массива по модулю не превосходят 109.
Выходные данные
Программа должна вывести М строчек. Для каждого числа из второго
списка нужно вывести номер его первого вхождения в первый список. Ну-
мерация начинается с единицы. Если число не входит в первый список,
нужно вывести одно число 0.
Sample Input 1:
5 3
10 15 23 23 50
1 10 23
Sample Output 1:
0
1
3
Sample Input 2:
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1179
Sample Output 2:
Модификации бинарного поиска 51
Правый двоичный поиск
Дано два списка чисел, числа в первом списке упорядочены по неубыва-
нию. Для каждого числа из второго списка определите номер последнего
появления этого числа в первом списке.
Входные данные
В11ервой строке входных данных записано два числа Л' и М (1 ЛК20000).
Во второй строке записано N упорядоченных по неубыванию целых чи-
сел — элементы первого списка. Все элементы массива по модулю не пре-
восходят 109.
В третьей строке записаны М целых неотрицательных чисел — элементы
второго списка. Все элементы массива по модулю не превосходят 109.
Выходные данные
Программа должна вывести М строчек. Для каждого числа из второго спи-
ска нужно вывести номер его последнего вхождения в первый список. Ну-
мерация начинается с единицы. Если число не входит в первый список,
нужно вывести одно число 0.
Sample Input:
5 3
10 15 23 23 50
1 10 23
Sample Output:
0
1
4
Sample Input 2:
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1179
52 Алгоритмы поиска
Sample Output 2:
10
4
7
2
0
Поиск
Напишите программу, которая определяет, сколько раз встречается задан-
ное число х в данном массиве.
Входные данные
3 первой строке задается одно натуральное число N, не превосходящее
2-1015.
Во второй строке вводятся N целых упорядоченных по неубыванию чи-
сел, каждое из которых по модулю не превосходит 10ь.
В третьей строке содержится одно целое число х, не превосходящее по
модулю 106.
Выходные данные
Вывести одно число — количество чисел, равных х.
Sample Input 1:
6
1 4 5 5 6 8
5
Sample Output 1:
2
Sample Input 2:
3
-10 5 10
5
Sample Output 2:
1
Модификации бинарною поиска 53
Sample Input 3:
4
2 3 3 3
3
Sample Output 3:
3
Поиск-2
Даны два массива. Для каждого элемента второго массива определите,
сколько раз он встречается в первом массиве.
Входные данные
Первая строка входных данных содержит одно число N( 1 < N С 105) — ко-
личество элементов в первом массиве.
Вторая строка содержит N целых упорядоченных по неубыванию чисел,
не превосходящих по модулю 10s — элементы первого массива.
Третья строка входных данных содержит одно число М(\ < М < 10е) — ко-
личество элементов во втором массиве.
Четвертая строка содержит М целых чисел, не превосходящих по модулю
10’ — элементы второго массива.
Выходные данные
Выведите М чисел: для каждого элемента второго массива выведите,
сколько раз такое значение встречается в первом массиве. * 3
Sample Input 1.
3
-10 10 10
3
-10 5 10
Sample Output 1:
10 2
54 Алгоритмы поиска
Sample Input 2:
3
112
4
С 1 2 3
Sample Output 2:
О 2 1 С
Sample Input 3:
3
13 5
7
0 1 2 3 4 5 6
Sample Output 3:
0 1 0 1 C 1 0
Приближенный двоичный поиск
Реализуйте алгоритм приближенного бинарного поиска.
Входные данные
В первой строке входных данных содержатся числа N и К N и К (1 < N,
100000.
Во второй строке задаются N чисел первого массива, отсортированного
по неубыванию
В третьей строке — К чисел в торого массива.
Каждое число в обоих массивах целое и по модулю не превосходит 2 • 109.
Выходные данные
Для каждого из К чисел выведите в отдельную строку число из первого
массива, наиболее близкое к данному. Если таких несколько, выведите
меньшее из них.
Модификаций бинарного поиска 55
Sample Input 1:
5 5
1 3 5 7 9
2 4 3 1 6
Sample Output 1:
1
3
7
1
5
Sample Input 2:
6 11
1 1 4 4 8120
1 2 3 4 5 6 7 8 63 64 65
Sample Output 2:
1
1
4
4
4
4
8
8
8
8
120
56 Алгоритмы поиска
Sampfe Input 3:
10 10
-5 1 1 3 5 5 8 12 13 16
0 3 7-17 23 11 0 11 15 7
Sample Output 3:
1
3
8
-5
16
12
1
12
16
8
Sample Input 4:
2 3
12000000000
-20000000002000000000 0
Sample Output 4;
1
2000000000
1
Поиск прыжками 0ump search) 57
Поиск прыжками (Jump search)
Проблема
Дана последовательность упорядоченных чисел, состоящая не более чем
из 2-10’ элементов. Доступ к элементам массива имеется только в одну
сторону, то есть либо слева направо, либо справа налево, то есть доступ не
произвольный.
Найти индекс элемента данной последовательности, который равен числу
х. Также в задаче есть ограничение по времени 500 ms, то есть половина
секунды.
Входные данные Выходные данные
7 -10 -5 4 6 9 10 11 10 5
5 -2 10 100 250 315 -2 0
5 -2 10 100 250 315 15 -1
Решения, которые приходят в первую очередь
• Использовать линейный поиск. Заметим, что если применить ли-
нейный поиск, то алгоритм будет работать в худшем случае за
О(п) = 0(10’). А как известно — это больше секунды, а точнее, не-
сколько секунд. Следовательно, использовать линейный поиск не
можем.
• Использовать бинарный поиск Заметим, что у нас есть ограничение:
мы не можем получать любые элементы, а можем получать только
последовательно. В бинарном поиске мы смещаемся то влево, то
вправо, следовательно, бинарный поиск не можем применить.
58 Алгоритмы поиска
Идея
Пусть дается следующий массив:
индексы 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
элементы 5 16 18 19 19 20 21 22 30 40 45 50 60 75 80
Далее разобьем массив на блоки по 3 элемента:
индексы 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
элементы 5 16 18 19 19 20 21 22 30 40 45 50 60 75 8С
Далее разобьем массив на блоки по 3 элемента:
Так как массив отсортирован (это очень важно), то с помощью «перепры -
гиваний через блоки» найдем блок, в котором может содержаться иско-
мый элемент (например, 45).
А затем пройдем по данному блоку линейно и найдем искомый элемент.
индексы О
элементы 5
1
16
14
ВО
Поиск прыжками (lump search) 59
Суть алгоритма поиска прыжками (Jump search)
Поиск прыжками—это поиск заданного элемента на упорядоченном множе
ствс, осуществляемый путем неоднократных перепрыгиваний вперед с фик-
сированным шагом. При каждом прыжке записывается предыдущий шаг.
Прыжки прекращаются, когда найден элемент больше искомого. Затем запу-
скаем линейный поиск между предыдущим и текущим шагами. Это уменьша-
ет поле поиска и делает линейный поиск жизнеспособным вариантом.
Алгоритм
Разобьем наш список элементов размера N на блоки размера В. Список
отсортирован по возрастанию.
• Шаг 1; Установим начало блока в индексе 0, а конец в индексе В-1.
• Шаг 2: Будем перемещаться слева направо, прибавляя к обоим
концам размер блока В, пока последний элемент текущего блока
меньше, чем искомый элемент.
• Шаг 3: Остановимся в блоке, где находится искомый элемент. Вы-
полним линейный поиск по данному блоку, чтобы найти искомый
элемент.
Реализация
Нужно пенять, какой размер блока подобрать. Для этого обратимся к ма-
тематике.
Если мы попытаемся записать сложность алгоритма, который мы описали
зыше, то получится следующее
Теперь давайте посмотрим, для какого значения Б это выражение имеет
минимум. Для этого мы дифференцируем (берем производную по В) по В
и приравниваем его к 0:
N = B2
B=\N
Итак, оптимальный размер прыжка yN.
60 Алгоритмы поиска
СИ
static int JumpSearch(int[] array, int x)
{
int В = (int) Math.Sqrt(array.Length); I! вычисляем
размер блока(прыжка)
int start =0; // начальная позиция блока
int end = В — 1; // конечная позиция блока
while (array[end] < х) // пока конец блока меньше
искомого элемента
{
if (end == ar г ay. Length — 1) // если дошли до
конца массива, выходим
{
break;
}
start = Math .Min (array.Length — 1, start + B) ;
// перемещаем начало блока вправо
erd = Math .Min (array. Length — 1, end + B) ;
// перемещаем конец блока вправо
}
if (х > array[end]) // если искомый элемент больше,
чем последний элемент блока, значит, не нашли нужный
элемент
{
return -1 ;
}
for (int i = end; i >= start; i—) // линейным поиском
проходим по найденчом.у блоку
{
if (array[i] == х) // если текущий элемент равен
искомому, то возвращаем его индекс
{
return i;
}
}
return -1; // если дошли досюда, значит, не нашли
в массиве искомый элемент
}
Поиск прыжками (Jump search) 61
Время работы
Временная сложность Время работы Комментарий
В лучшем 0(1) 3 лучшем случае, когда искомый элемент находится при первом сравнении
В среднем 0(>/л) В среднем этот алгоритм требует л'л итераций цикла
В худшем O(Vn) Худшему случаю соответствуют две ситуации: искомый элемент находится в последней итерации цикла или он вовсе отсутствует в массиве
Применимость
Применяется на упорядоченном массиве элементов при ограниченном
времени выполнения. Если количество элементов не превышает 109и нам
важно время выполнения, можно воспользоваться данным поиском.
Этот поиск также используется вместо бинарного поиска, когда прыжки
в обратную сторону затратны.
Преимущества и недостатки
Преимущества Недостатки
Относительно прост б реализации Применяется только на упорядоченном множестве
Используется, если множество содержит большое количество элементов Не может работать в потоковом режиме при непосредственном получении данных из любого исгочника
Не I ребуе т дополни тельной памяти
Быстрота выполнения поиска
Просмотр элементов происходит только в одном направлении
62 Алгоритмы поиска
Задачи
Jump search
Реализуйте алгоритм поиска прыжками (Jump search).
Входные данные
В первой строке входных данных содержатся натуральные числа N и К
(1 < N, К 1000G0).
Во второй строке задаются Л' элементов первою массива, отсортирован-
ного по возрастанию.
В третьей строке — К элементов второго массива.
Элементы обоих массивов — целые числа, каждое из которых по модулю
не превосходит 10’.
Выходные данные
Требуется для каждого из К чисел вывести в отдельную строку YES, если
это число встречается в первом массиве, и NO в противном случае.
Sample Input 1:
10 5
1 2 3 4 5 6 7 6 9 10
-2 0 4 9 12
Sample Output 1:
NO
NO
YES
YES
NO
Sample Input 2:
10 10
1 61126 21728766127391629812671268^1000000000
1006127 1 61200-10000 1217 1000010C0000000
Поиск прыжками (Jump search) 63
Sample Output 2:
NC
YES
YES
YES
NC
NO
YES
YES
NC
YES
Sample Input 3:
10 10
-8-6 -4-4 -2-1 0 2 3 3
8 3-3 -2 2-1 2 9-8 0
Sample Output 3:
NO
YES
NC
YES
YES
YES
YES
NO
YES
YES
64 Алгоритмы поиска
Модификации поиска прыжками
(Jump search)
В массиве может встречаться несколько элементов со значениями, рав-
ными искомому. Рассмотренный ранее алгоритм находит первый эле-
мент, совпавший с искомым, который в порядке следования в массиве
может быть ни первым, ни последним среди равных искомому. Например,
в массиве чисел [1,5,5,5,5,5,5,7,81 искомый элемент х = 5 совпадет с эле-
ментом с индексом 3, который не относится ни к первому, ни к последнему
элементу, равному искомому.
Существуют две модификации рассматриваемого алгоритма для поиска
первого и последнего вхождения искомого элемента. Все зависит от того,
какой инвариант мы выберем.
Нахождение самого левого вхождения
Идея
При равенстве последнего элемента текущего блока с искомым будем
останавливаться. После нахождения нужного блока пройдемся с начала
блока к концу и найдем первый попавшийся элемент, равный искомому
Давайте посмотрим наглядно, как будет работать алгоритм:
i индексация номер ите- рации 0 1 2 3 4 5 6 7 8 start, end
1 1 5 5 5 5 5 5 7 8 start = 0, end = 2
В первой же итерации мы вышли с цикла,
который находит нужный блок (start =0,
end~2). Далее в этом блоке пройдемся
слева направо линейно и найдем первый
элемент, который равен х = 5. Таким об-
разом, подобным алгоритмом найдем
элемент с индексом 1, который равен ис-
комому.
Модификации поиска прыжками (Jump search) 65
Реализация
................................ c#.............
static int JumpSearch(int[] array, int x)
{
int В = (int) Math.Sqrt(array.Length); // вычисляем
размер блока(прыжка)
int start. = 0; // начальная позиция блока
int end = В — 1; // конечная позиция блока
while (array[end] < х) // пока конец блока меньше
искомого элемента. Прервемся при равенстве
{
if (end == array.Length — 1) // если дошли дс
конца массива, выходим
{
break;
}
start = Mach .Min (array. Length — 1, start + B) ;
// перемешаем начало блока вправо
end = Math.Min (array.Length — 1, end + Б);
// перемещаем конец блока вправо
}
if (х > array[end]) // если искомый элемент больше,
чем последний элемент блока, значит, не нашли нужный
элемент
{
return -1;
}
for (int i = start; i <= end; i++) // линейным поиском
слева направо проходим по найденному блоку
(
if (array[i] == х) // если текущий элемент равен
искомому, то возвращаем его индекс
{
return i;
}
}
return -1; // если дошли досюда, значит, не нашли
нужного элемента в массиве
}
66 Алгоритмы поиска
Нахождение самого правого вхождения
Идея
При равенстве последнего элемента текущего блока с искомым будем
переходить к следующему блоку, ведь нам нужно найти самый послед-
ний элемент, который равен искомому. Но при этом нам нужно знать, что
в следующем блоке есть элемент, равный искомому. Это условие нужно
проверять обязательно, так как мы могли попасть на последний элемент
з блоке, который равен искомому. Если мы не проверим данное условие,
то перейдем в следующий блок, где нет искомого элемента. После нахож-
дения нужного блока, пройдемся с конца блока к началу и найдем первый
попавшийся элемент, равный искомому.
Давайте посмотрим наглядно, как будет работать алгоритм:
i индексация номер итерации 0 1 2 3 4 5 6 7 8 start, end
1 1 5 5 5 5 5 5 7 8 start = 0, end = 2
2 1 5 5 5 5 5 5 7 8 start = 3, end = 5
3 1 5 5 5 5 5 5 7 8 start = 6, end = 8
По алгоритму найдем нужный блок (start-6, end-8). Далее в этом блоке
пройдемся справа налево линейно и найдем первый элемент, который ра-
вен №=5. Таким образом, подобным алгоритмом найдем элемент с индек-
сом 6, который равен искомому.
Модификации поиска прыжками (Jump search) 67
Реализация
c#
static int JumpSearch(int[J array, int x)
{
int В = (int) Math.Sort(array.Length); // вычисляем
размер блока(прыжка)
int start = 0; // начальная позиция блока
int end = В — 1; // конечная позиция блока
while (array[end] <= х end < array.Length — 1
SS array[end + 1] <= x) // пока конец блока меньше либо
равен искомому элементу и в следующем блоке есть такой же
элемент
1
start = Math.Min (array.Length — 1, start + B) ;
// перемещаем начало блока вправо
end = Math.Min (array.Length — 1, end + B) ;
// перемещаем конец блока вправо
}
if (х > array[end]) // если искомый элемент больше,
чем последний элемент блока, значит, не нашли нужный
элемент
{
return -1;
}
for (int i = end; i >= start; i—) // линейным поиском
справа налево проходим по найденному блоку
if (array[i] == х) // если текущий элемент равен
искомому, то возвращаем его индекс
{
return i;
}
}
return -1; // если дошли досюда, значит, не кашли
нужный элемент в массиве
}
68 Алгорит мы поиска
Задачи
Первое вхождение
Дано два списка чисел, числа в первом списке упорядочены по неубыва-
нию. Для каждого числа из второго списка определите номер первого по-
явления этого числа в первом списке.
Входные данные
В первой строке входных данных записано два числа N и М (1 < N,
ЛК 20000).
Во второй строке записано N упорядоченных по неубыванию целых чи
сел — элементы первого списка.
В третьей строке записаны М целых неотрицательных чисел — элементы
второго списка.
Элементы обоих массивов — целые числа, каждое из которых по модулю
не превосходит 10у.
Выходные данные
Программа должна вывести Л7 строчек. Для каждого числа из второго
списка нужно вывести номер его первого вхождения в первый список. Ну-
мерация начинается с единицы. Если число не входит в первый список,
нужно вывести одно число 0.
Sample Input 1:
5 3
10 15 23 23 50
1 10 23
Sample Oulput 1;
0
1
3
Модификации поиска прыжками (Jump search) 69
Sample Input 2:
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1179
Sample Output 2:
10
3
7
1
0
Sample Input 3:
1 1
0
0
Sample Output 3:
1
Последнее вхождение
Дано два списка чисел, числа е первом списке упорядочены по неубыва-
нию. Для каждого числа из второго списка определите номер последнего
появления этого числа в первом списке.
Входные данные
В первой строке входных данных записано два числа N и М (1 < N,
М С 20000).
Во второй строке записано N упорядоченных по неубыванию целых чи-
сел — элементы первого списка.
В третьей строке записаны М целых неотрицательных чисел — элементы
второго списка.
Элементы обоих массивов — целые числа, каждое из которых по модулю
не превосходит 109.
70 А лгоритмы поиска
Выходные данные
Программа должна вывести М строчек. Для каждого числа из второго спи-
ска нужно вывести номер его последнего вхождения р первый список. Ну-
мерация начинается с единицы. Если число нс входит в первый список,
нужно вывести одно число 0.
Sample Input 1:
5 3
10 15 23 23 50
1 10 23
Sample Output 1:
о
1
4
Sample Input 2:
2 1
0 0
0
Sample Output 2:
2
Поиск
Напишите программу, которая определяет, сколько раз встречается задан-
ное число х в данном массиве.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
2 -1015.
Во второй строке вводятся N целых упорядоченных по неубыванию чи-
сел, каждое из которых по модулю не превосходит 106.
В третьей строке содержится одно целее число х, не превосходящее по
модулю 106
Сравнение алгоритмов поиска 71
Выходные данные
Вывести одно число — количество чисел, равных х.
Sample Input 1:
6
1 4 5 5 6 8
5
Sample Output 1:
2
Sample Input 2:
3
-10 5 10
5
Sample Output 2:
1
Sample Input 3:
4
2 3 3 3
3
Sample Output 3:
3
Сравнение алгоритмов поиска
Линейный поиск сканирует один элемент за другим, не перепрыгивая ни
через какой элемент.
• Наихудшая сложность — О(л);
• Время, затрачиваемое на поиск элементов, увеличивается с увели-
чением количества элементов.
72 Алгоритмы поиска
С помощью поиска прыжками не сканируются все элементы. Мы с помо-
щью прыжков длины л л находим блок, где находится целевой элемент. За-
тем с помощью линейного поиска найдем искомый элемент.
• Наихудшая сложность — О(л/л);
• Требует упорядоченных данных, чт обы перепрыгивать через блоки.
Бинарный поиск сокращает поиск до половины каждый раз, пока вы не
найдете требуемый элемент или не просмотрите все,
• 11аихудшая сложность — О(1од л);
• Каждый раз ищется средний элемент, чтобы сравнить его с иско-
мым значением.
Важные различия
• Входные данные должны быть отсортированы в бинарном поиске
и в поиске прыжками, а не в линейном поиске В линейном поиске
сортировка данных не требуется.
• Линейный поиск осуществляет последовательный доступ, тогда
как бинарный поиск осуществляет случайный доступ к данным. По-
иск прыжками с помощью прыжков осушесгвляет тоже последова-
тельный доступ по блокам.
• Временная сложность линейного поиска — О(л), поиск прыжками
имеет временную сложность О( vn), а двоичный поиск имеет вре -
менную сложность О(1од п).
• Линейный поиск выполняет сравнение на равенство, а бинарный
поиск и поиск прыжками выполняет сравнение на основе порядка.
Линейный поиск Поиск прыжками Бинарный поиск
Требует упорядоченность данных нет да да
Просмотр всех элементов да нет нет
Требует случайный (произвольный) доступ к данным нет нет да
Сравнение равенство порядок порядок
Временная сложность ОД ООД О(/ор л)
Выбор алгоритма поиска 73
Выбор алгоритма поиска
Среди такого многообразия алгоритмов поиска хочется иметь алгоритм,
по которому можно бы было подобрать нужный алгоритм поиска к любой
задаче. Давайте выпишем еще раз, от чего может зависеть ^ыбор того или
иного алгоритма поиска:
1. количество элементов во входной последовательности;
2. упорядоченность данных;
3. произвольный доступ к элементам входной последовательности.
На основании приведенных выше факторов ниже приведен алгоритм вы-
бора алгоритмов поиска в виде блок-схемы:
74 Алгоритмы поиска
Для тех, кто забыл (или не знал), как читаются блок-схемы:
1. читаем сверху вниз, начиная с овала;
2. фигуры в виде ромба представляют условия. Соответственно, ус
ловие может быть истинно (переходим по стрелке Yes) либо ложно
(переходим по стрелке No),
3. прямоугольник показывает выбор алгоритма поиска.
Прокомментирую блок-схему:
• если входные данные не отсортированы (упорядочены), то ис-
пользуем линейный поиск, так как остальные два поиска работают
только с упорядоченными данными;
• если данные отсортированы и количество входных данных не-
много (зависит от конкретной задачи), то используем линейный
поиск, так как при небольших данных линейный поиск будет вы
полнен быстро. Также аргументом в пользу выбора линейного по-
иска является простота реализации, ибо зачем писать сложный по
реализации алгоритм поиска для небольшого количества входных
данных;
• если данные отсортированы, количество входных данных велико
(линейный поиск не устраивает по времени выполнения), то нуж-
но ориентироваться на возможность произвольного доступа к эле-
ментам. 1£сли произвольный доступ к элементам есть, используем
бинарный поиск, если нет произвольного доступа к элементам, то
используем поиск прыжками.
Алгоритмы сортировки данных
Общая информация о сортировках
Прежде чем углубимся в разные алгоритмы сортировки данных, давайте
остановимся и рассмотрим процесс сортировки предметов или объектов.
Для этого обсуждения давайте представим, что нам нужно отсортировать
стопку надувных шаров.
Чтобы надувные шарики хорошо выглядели
и правильно сидели внутри трубки, мы хотим
разместить более крупные из них снизу, а более
мелкие — сверху, то есть в порядке возрастания
или от наименьшего к наибольшему, если смо-
треть сверху вниз.
Теперь, когда есть ментальная картина, наша
задача отсортировать шарики, поместив самые
большие внизу и самые маленькие сверху. Поду-
майте, как вы будете решать данную задачу?
Скорее всего, вы прилете к одному из следую-
щих решений:
1. Найдете наибольший надувной мяч и по -
стараетесь поместить его на дно (в самый
низ). Затем следующий наибольший мяч,
который поместите на предпоследнем
месте. И так вы доберетесь до самого
верхнего мяча.
76
Алгоритмы сортировки данных
2. Найдете самый маленький мяч и положите его на вершину. Затем
следующий наименьший мяч, который поместите на втором месте.
И так вы доберетесь до самого нижнего мяча.
В любом случае вы выполните ручную сортировку. Вы будете сравнивать
размеры надувных шариков на глаз.
В компьютерной программе нет «визуальной» способности
Ф видеть самый большой из надувных шариков. Вы должны
иметь дело с размерными факторами, то есть нужен способ
сравнить один элемент с другим по размеру. Например,
с шариками можно использовать диаметр шаров, чтобы
сравнить два шара.
Алгоритм сортировки — это алгоритм для упорядочивания элементов
в списке.
Пусть элементами списка являются шарики. Шарик-- это реальный объект
в жизни, который имеет много свойств Например: цвет, диаметр, степень
упругости:
Для таких сложных объектов (имеет более 1 свойства) нужно понять, от-
носительно какого свойства или свойств ориентироваться, чтобы сравнить
два шарика.
Ф Свойство, служащее критерием порядка, называется клю-
чом сортировки.
На практике в качестве ключа часто выступает число, а в остальных по-
лях хранятся какие-либо данные, никак не влияющие на работу' алгоритма.
Общая информация о сортировках 77
В примере с шариками в качестве ключа сортировки выступает диаметр
шариков:
Объект Шарик
Свойства Цвет
Диаметр «**'
Степень упругости
...
Ключ сортировки
Свойства алгоритмов сортировки
• Устойчивая (стабильная) сортировка — сортировка; которая не
меняет относительный порядок сортируемых элементов, имеющих
одинаковые ключи. Устойчивость является очень важной характе-
ристикой алгоритма сортировки, гак как не дает дополнительные
расходы при перемещении элементов с одинаковыми ключами.
• Ешё одним важным свойством алгоритма является его сфера при-
менения Здесь два основных типа упорядоченияф
о Внутренняя сортировка оперирует массивами, целиком поме-
щающимися в оперативной памяти с произвольным доступом
к любой ячейке. Данные обычно упорядочиваются на том же
месте без дополнительных затрат памяти.
о Внешняя сортировка оперирует1 запоминающими устройства-
ми большого объема, но не с произвольным доступом, а после-
довательным (упорядочение файлов), то есть б данный момент
«виден» только один элемент, а затраты на перемотку по срав-
нению с памятью неоправданно велики. Кроме того, доступ
к данным во внешней памяти производится намного медлен-
нее, чем операции с оперативной памятью.
• Доступ к носителю осуществляется последовательным образом,
в каждый момент времени можно считать или записать только эле-
мент, следующий за текущим.
78 Алгоритмы сортировки данных
• Объем данных не позволяет им разместиться в ОЗУ.
• Естественность поведения — эффективность алгоритма при об-
работке уже упорядоченных или частично упорядоченных данных.
Если алгоритм выполняется быстрее обычного с такими данными,
то алгоритм применяется чаще.
В рамках книги будем использовать числа, так как они легко представле-
ны в простых программах и хороши для преподавания концепций. Но вы
должны понимать, что вместо чисел может быть что угодно. Главное, что
бы эти объекты можно было сравнить по какому-нибудь свойству.
Сортировка пузырьком
Проблема
Дана последовательность чисел, состоящая не более чем из 104 элементов.
Необходимо упорядочить числа по неубыванию.
Пример 1.
Входные данные:
4-10 11 8 6 10-5
Выходные данные:
-10-5 4 6 8 10 11
Пример 2.
Входные данные:
10 8 2 8 6 0 1
выходные данные:
0 1 2 б 8 8 10
Сортировка пузырьком 79
Идея сортировки пузырьком (Bubble Sort)
Пройдемся по нашей последовательности и найдем самый большой эле-
мент и поставим на последнее место в последовательности. Затем прой-
демся еще раз и найдем самый большой элемент, не считая последний
элемент, и поставим его на предпоследнее место. И так далее, пока не до-
стигнем начала.
Находить наибольший элемент будем с помощью сравнений рядом стоя-
щих элементов. Если пара элементов находится не в том порядке (левый
элемент больше, чем правый), то меняем их местами. С помощью таких
сравнений очередных пар мы поместим наибольший элемент в конце спи-
ска. При каждом проходе очередной наибольший элемент массива ставит-
ся на свое место в конце массива рядом с предыдущим «наибольшим эле-
ментом», а наименьший элемент перемещается на одну позицию к началу
массива («всплывает» до нужной позиции, как пузырек в воле — отсюда
и название алгоритма).
Наглядный пример работы сортировки пузырьком.
soil
Алгоритм
Алгоритм состоит из повторяющихся проходе! по сортируемому масси-
ву. За каждый проход элементы последовательно сравниваются попарно
и, если порядок в паре неверный, выполняется обмен элементов. Прохо
ды по массиву повторяются N — 1 раз. При каждом проходе алгоритма
очередной наибольший элемент массива ставится на свое место в конце
массива рядом с предыдущим «наибольшим элементом», а наименьший
элемент перемещается на одну позицию к началу массива.
Наглядный пример
Дан неотсортированный список чисел 3,1, 4,6, 7, 5, 2. Необходимо отсор
тировать числа по возрас ганию.
При первом проходе сначала сравниваются 3 и 1. Числа стоят в неправиль-
ном порядке, потому что 3 больше 1. Следовательно, происходит обмен
элементов и список будет иметь вид 1,3, 4,6, 7, 5, 2.
8<Алгоритмы сортировки данных
Далее сравниваются 3 и 4. Они стоят в правильном порядке. Далее сравни-
ваются 4 и 6, которые стоят также в правильном порядке. Далее сравнива-
ются 6 и 7, которые стоят также в правильном порядке.
Далее сравниваются 7 и 5, которые стоят в неправильном порядке. Следо-
вательно, происходит обмен элементов и список будет иметь вид 1, 3,4,6,
5, 7, 2.
Далее сравниваются 7 и 2, которые стоят в неправильном порядке. Следо-
вательно, происходит обмен элементов и список будет иметь вид 1,3,4,6,
5, 2, 7.
Проход весь закончился, который дал нам наибольший элемент в конце
списка.
Теперь делаем следующий проход и находим следующий наибольший эле-
мент на предпоследнем месте.
Далее сравниваются 1 и 3 Они стоят в правильном порядке. Далее сравни-
ваются 3 и 4, которые стоят также в правильном порядке. Далее сравиива
ются 4 и 6, которые стоят также в правильном порядке.
Далее сравниваются 6 и 5, которые стоят в неправильном порядке. Следо -
вательно, происходит обмен элементов и список будет иметь вид 1.3,4,5,
6,2,7.
Далее сравниваются 6 и 2, которые стоят в неправильном порядке. Следо-
вательно происходит обмен элементов и список будет иметь вид 1,3, 4; 5,
2,6,7.
Проход весь закончился, который дал нам следующий наибольший эле-
мент на предпоследнем месте списка.
Если такие действия повторить N — 1 раз, то получим отсортированный
список элементов.
Сортировка пузырьком 81
Реализация
си
static void BvbbleSort(int[] array)
{
for (int i = array.Length — 1; i > 0; i—) // на какое
место будем ставим наибольший элемент
{
for (int j = 0; j < i; j++) // проходим no
неотсортированной последовательности
{
if (array[j] > array+ 1])// если порядок
элементов неправильный
(
// меняем местами пары
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
)
}
Реализация с оптимизацией
Можно заметить, что если на одном из оче-
редных проходов окажется, что обмены
больше не нужны, то это будет означать,
что нее элементы находятся на своих ме-
стах, то есть массив отсортирован. Тогда
давайте перед очередным проходом по
ставим переменную флажок, по которому
будем понимать, были ли перестановки
элементов. Изменим значение флажка
при обмене элементов. Если после цикла
флажок останется в том же состоянии, как
до прохода, значит, массив отсортирован
и пора прекращать проходы.
82 Алгоритмы сортировки данных
C#
static void BubbleSort(int[] array)
{
for (int i = array.Length — 1; i > 0; i—) // на какое
место будем ставить наибольший элемент
{
bool flag = false; // false — не было обменов,
true — был хотя бы 1 обмен
for (int j = 0; j < i; j++) // проходим no
неотсортированной последовательности
{
if (arraytj] > array[j + 1J)// если порядок
элементов неправильный
{
// меняем местами пары
int temp = arraytj];
array[j] = array[j + 1];
arraytj +1] = temp;
flag = true; // меняем флажок
}
}
if (flag == false) // если значение флага не
поменялось
{
return; II массив отсортирован. Выхсдим
с функции
}
}
}
Свойства алгоритма сортировки пузырьком
Свойство Ответ комментарий
Устойчивость Да При равенстве элементов не происходит переупорядочивания элементов
Внутренняя/внешняя сортировка Внутренняя Нужно несколько раз пробегать по последо! >ате льности
Естественность поведения Да При частичном сортированном массиве алгоритм не будет менять их относительный порядок и сработает быстрее обычного
Сортировка пузырьком 83
Время работы
При анализе пузырьковой сортировки стоит отметить, что, вне зависимо-
сти от первоначального порядка элементов, для списка из п элементов бу-
дет сделан л-1 проход.
Табличный анализ для сортировки пузырьком
Номер прохода по массиву Количество сравнений
1 л-1
2 л-2
3 л-3
...
Л-1 1
По таблице выше видно число сравнений при каждом проходе. Посчитаем
обшее количество сравнений, то есть просуммируем все значения. Заме-
тим, что данные числа представляют собой арифметическую последова-
тельность, которую можем посчитать по формуле:
(первый элемент + последний элемент) • количество элементов
Подставим значения и получим.
(1 + (п - 1)) • (п - 1) п • (п — 1) п* 2 — п 1 _ 1
----------Д---------- =----7Г-— = —-— = — п£ — - п
2--------------------2 2 2 2
То есть, если убрать константы и слагаемые меньшей степени, получится
асимптотическая сложност ь (9(л?).
84 Алгоритмы сортировки данных
Временная сложность Время работы Комментарий
В лучшем О(л) В лучшем случае, когда список уже отсортирован. Делаем J проход, чтобы убедиться, что данные упорядочены
В среднем О(л2) В среднем этот алгоритм требует п2 итераций цикла
В худшем О(л2) В худшем случае, когда список уже отсортирован в обратном порядке, чем нужно
Применимость
Так как алгоритм очень прост, поэтому вполне допустимо применение сор-
тировки пузырьком для множества задач с последовательностями малой
и средней размерности, где время выполнения алгоритма не играет суще-
ственной роли.
Поскольку пузырьковая сортировка делает проход по всей неотсортиро-
ванной части списка, она умеет то, что не могут большинство сортировоч-
ных алгоритмов. В частности, если во время прохода не было сделано ни
одной перестановки, то мы знаем, что список уже отсортирован. Таким
образом, алгоритм может быть модифицирован, чтобы останавливаться
раньше, если обнаруживает, что задача выполнена. То есть для списков,
которым нужно всего несколько проходов, пузырьковая сортировка име-
ет преимущество, поскольку умеет распознать отсортированный список
и остановиться.
Преимущества и недостатки
Преимущества Недостатки
Прост в реализации Сложность по времени
Алгоритм умеет определять на промежуточном этапе отсортирована ли последовательность Используется только на маленьких и средних последовательностях
Не требует дополнительней памяти
Сортировка пузырьком 85
Задачи
Неубывание
Напишите программу, которая сортирует массив по неубыванию, с помо-
щью сортировки пузырьком.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
1000 — размер массива.
Во второй строке вводятся N целых чисел, каждое из которых по модулю
не превосходит 10ОО — элементы массива.
Выходные данные
Вывести отсортированный по неубыванию массив на одной строке через
пробел.
Примечание:
Неубывание — это когда числа равны или возрастают.
Sample Input 1:
5
15 1 5568 13
Sample Output 1:
1 5 13 15568
Sample Input 2:
1
1
Sample Output 2:
1
Sample Input 3:
2
3 1
Sample Output 3:
1 3
86 Алгоритмы сортировки данных
Невозрастание
Напишите программу, которая сортирует массив по невозрастанию с по-
мощью сортировки пузырьком.
Входные данные
В первой строке задается одно натуральное число W, не превосходящее
10ОО — размер массива.
Во второй строке вводятся N целых чисел, каждое из которых по модулю
не превосходит 1000 — элементы массива.
Выходные данные
Вывести отсортированный по невозрастанию массив на одной строке че-
рез пробел.
Примечание:
Невозрастание — это когда числа равны или убывают.
Sample Input:
5
15 1 5568 13
Sample Output:
568 15 13 5 1
Сортировка пузырьком 87
Количество обменов
Дан массив целых чисел. Определите, сколько обменов сделает алгоритм
пузырьковой сортировки по возрастанию для данного массива.
Зходные данные
На первой строке дано число N (1 < N С 1600) - количество элементов
в массиве.
Во второй строке вводятся N целых чисел, каждое из которых по модулю
не превосходит 10’. Гарантируется, что все элементы массива различны.
Выходные данные
Выведите одно число — количество обменов пузырьковой сортировки.
Sample Input 1:
5
15 1 5568 13
Sample Output 1:
4
Sample Input 2:
3
12 3
Sample Output 2:
0
Sample Input 3:
5
1 2 3 4 5
Sample Output 3:
0
88 Алгоритмы сортирсвки данных
Средний балл
В 39 школе в 7-м «Б» классе учатся N учеников. Недавно они писали по-
лугодовые работы по информатике, математике и физике. Вам известны
оценки каждого ученика по каждому из предметов. Выведите фамилии
и имена учащихся в порядке невозрастания их среднего балла.
Входные данные
На первой строке дано число N (1 < N < 100 000) — количество учеников.
В следующих Л' строках заданы фамилия, имя и три числа (оценки по
трем предметам: информатике, математике и физике). Данные в каждой из
строк разделены одним пробелом. Оценки принимают значение от 1 до 5.
Выходные данные
Необходимо вывести пары фамилия-имя но одной на строке, разделяя фа
милию и имя одним пробелом.
Выводить оценки не нужно.
Если несколько учащихся имеют одинаковые средние баллы, то их нужно
выводить в порядке, заданном во входных данных.
Sample Input 1:
3
Petrov Petr 333
Dzeranov Iosif 555
Guev Timur 555
Sample Output 1:
Dzeranov Iosif
Guev Timur
Petrov Petr
Sample Input 2:
1
Kozlov Georgiy 555
Sample Output 2:
Kozlov Georgiy
Сортировка пузырьком 89
Лучшие
В 39 школе в 7-м «Б» классе учатся N учеников. 11едавно они писали прове-
рочную работу по информатике. Определите трех учеников с наилучшими
баллами. Выведите фамилии и имена этих учащихся в порядке убывания
их балле в. Известно, что у всех учеников разные баллы.
Входные данные
На первой строке дано число N (3 CV < 100 000) — количество учеников.
В следующих Л' строках заданы фамилия, имя и балл ио информатике.
Данные в каждой из строк разделены одним пробелом. Балл — это целое
значение от 1 до 100000.
Выходные данные
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фа-
милию и имя одним пробелом. Выводить оценки не нужно.
Sample Input 1:
3
Petrov Petr 3
Dzeranov Iosif 5
Guev Timur 4
Sample Output 1:
Dzeranov Iosif
Guev Timur
Petrov Petr
Sample Input 2:
4
Petrov Petr 3
Dzeranov Iosif 5
Guev Timur 4
Fetrov2 Petr 6
90 Алгоритмы сортировки данных
Sample Output 2:
Petrov2 Petr
Dzeranov lesif
Guev Timur
Сортировка выбором
Проблема
Дана последовательность чисел, состоящая не более чем из 104 элементов.
Необходимо упорядочить числа по неубыванию
Пример 1.
Входные данные:
4-10 11 8 б 10-5
Выходные данные:
-10-5 4 6 8 10 11
Пример 2.
Входные данные:
10 8 2 8 б 0 1
выходные данные:
0 1 2 6 8 8 10
Идея сортировки выбором
Сортировка выбором улучшает пузырьковую сортировку, совершая всего
один обмен за каждый проход по списку. Для этого алгоритм ищет наи-
больший элемент и помещает его на соответствующую позицию. Как и для
пузырьковой сортировки, после первого прохода самый большой элемент
находится на правильном месте. После второго на свое место становится
следующий наибольший элемент. Процесс продолжается, требуя п-1 про-
ходов для сортировки п элементов, поскольку последний из них автомата
чески оказывается на своем месте.
Сортировка выбором 91
Алгоритм
Алгоритм состоит из повторяющихся проходов по сортируемому массиву.
За каждый прохсд находится наибольший элемент и выполняется один об-
мен наибольшего элемента и элемента на соответствующей позиции. Про-
ходы со массиву повторяются N — 1 раз. При каждом проходе алгоритма
очередной наибольший элемент массива ставится на свое место в конце
массива рядом с предыдущим «наибольшим элементом».
Наглядный пример
с пошаговым разбором
Дан неотсортированный список чисел 3, 1, 4, 6, 7, 5, 2. Необходимо
отсортировать числа по возрастанию.
Решение:
При первом проходе найдем максимальное значение среди всех элемен-
тов массива, то есть 7. Поменяем местами 7 и элемент, который стоит на
последнем месте (2): 3,1,4,6,2,5,7. Первый проход закончился, который
дал нам наибольший элемент в конце списка
Делаем второй проход и находим следующий наибольший элемент среди
всех элементов, кроме последнего, и поменяем местами с предпоследним
элементом. Наибольший элемент равен 6. Сделаем обмен: 3,1,4,5,2,6,7.
Делаем третий проход и находим следующий наибольший элемент сре-
ди всех элементов, кроме последних двух, и поменяем местами с соответ-
ствующим элементом. Наибольший элемент равен 5 Сделаем обмен: 3,1,
4,2,5,6,7.
Делаем четвертый проход и находим следующий наибольший элемент
среди всех элементов, кооме последних трех, и поменяем местами с соот-
ветствующим элементом. Наибольший элемент равен 4. Сделаем обмен:
3,1,2,4,5,6,7.
Делаем пятый проход и находим следующий наибольший элемент среди
всех элементе з, кром.е последних четырех, и поменяем местами с соответ-
ствующим элементом. Наибольший элемент равен 3. Сделаем обмен: 2,1,
3,4,5,6,7.
92 Алгоритмы сортировки данных
Делаем шестой и последний проход и находим следующий наибольший
элемент среди всех элементов, креме последних пяти, и поменяем места-
ми с соответствующим элементом. Наибольший элемент равен 2. Сделаем
обмен: 1,2,3,4,5,6,7.
Таким образом, массив отсортирован.
Реализация
с#
static void SelectionSort(int[] array)
{
for (int i = array.Length — 1; i > 0; i—) // на какое
место будем ставить наибольший элемент
(
int maxindex = i; // индекс максимального элемента
for (int j = 0; j < i; j++) // проходим ко
неотсортированной последовательности
{
if (array[j] > array [maxlr.dex])// ищем
максимальный элемент
{
maxindex = j; // запоминаем индекс
}
}
// если нашли максимальный элемент, отличный ст
текущего числа
if (maxindex!= i)
{
// меняем местами
int temp = array[maxindex];
array[maxindex] = array[i];
array[i] = temp;
}
}
}
Сортировка выбором 93
Свойства алгоритма сортировки выбором
Свойство Ответ Комментарий
Устойчивость Нет При перестановке элементов нельзя гарантировать, что не поменяются элементы с одинаковыми ключами
Внутренняя/внешняя сортировка Внутренняя Нужно несколько раз пробегать по последовательности
Естественность поведения Нет Каждый раз нужно находить максимальный элемент
Время работы
При анализе сортировки выбором стоит отметить, что, вне зависимости
от первоначального порядка элементов, для списка из п элементов будет
сделан л-1 проход.
Табличный анализ для сортировки выбором
Номер прохода по массиву Количество сравнений
1 л-1
2 л-2
3 л-3
...
л-1 1
Табличный анализ показывает число сравнений при каждом проходе. По-
считаем общее количество сравнений, то есть просуммируем все значе-
ния. Заметим, что данные числа представляют из себя арифметическую
последовательность, которую можем посчитать г.о формуле:
(первый элемент+последний элемент)количество элементе»
2
94 Алгоритмы сортировки данных
Подстаним значения и получим:
(1 + (п - 1)) • (п - 1) п (п - 1) п2 — п 1 , 1
------------ = Z = X-= ТГ — — п
2--------------------------------------------2-2-2 2
То есть, если убрать константы и слагаемые меньшей степени, получится
асимптотическая сложность О(л2).
Временная сложность Время работы Комментарий
Лучшее О(л2) Алгоритм всегда находит максимальный элемент на каждом проходе, независимо от упорядоченности элементов
В среднем О(и2) В среднем это т алгоритм требует п2 итераций цикла
В худшем О(ла) Алгоритм всегда находит максимальный элемент на каждом проходе
Применимость
Так как алгоритм очень прост, поэтому вполне допустимо применение
сортировки выбором для множества задач с последовательностями малой
и средней размерности, где время выполнения алгоритма не играет суще-
ственной роли.
Алгоритм используется в задачах, где обмены элементов затратны, по-
скольку сортировка выбором минимизирует количество обменов,-
Преимущества и недостатки
Преимущества Недостатки
Прост в реализации Сложность по времени
Не требует дополнительной памяти Используется только на маленьких и средних последовательностях
Минимизирует количество обменов Плохо работает с упорядоченными или частично упорядоченными данными
Сортировка выбором 95
Задачи
Неубывание
Напишите программу, которая сортирует массив по неубыванию, с помо-
щью сортировки выбором.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
1000 — размер массива.
Во второй строке вводятся N целых чисел, каждое из которых по модулю
не превосходит 1000 — элементы массива.
Выходные данные
Вывести отсортированный по неубыванию массив на одной строке через
пробел.
Примечание:
Неубывание — это когда числа равны или возрастают.
Sample Input:
5
15 1 5568 13
Sample Output:
1 5 13 15568
Невозрастание
Напишите программу, которая сортирует массив по невозрастанию, с по-
мощью сортировки выбором.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
1000 — размер массива.
Во второй строке вводятся N целых чисел, каждое из которых по модулю
не превосходит 1000 — элементы массива.
96 Алгоритмы сортировки данных
Выходные данные
Вывести отсортированный по невозрастанию массив на одной строке че-
рез пробел.
Примечание:
Невозрастание — это когда числа равны или убывают.
Sample Input:
5
15 1 5568 13
Sample Output:
568 15 13 5 1
Лучшие
В 39 школе в 7-м «Б» классе учатся Wучеников. Недавно они писали прове-
рочную работу по информатике. Определите трех учеников с наилучцгими
баллами. Выведите фамилии и имена этих учащихся в порядке убывания
их баллов. Известно, что у всех учеников разные баллы.
Входные данные
11а первой строке дано число N (3 < N 00 000) — количество учеников.
В следующих N строках заданы фамилия, имя и балл по информатике.
Данные в каждой из строк разделены одним пробелом Балл — это целое
значение от 1 до 100000.
Выходные данные
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фа-
милию и имя одним пробелом. Выводить оценки не нужно.
Sample Input 1:
3
Petrov Petr 3
Dzeranov Iosif 5
Guev Timur 4
Сортировка простыми вставками 97
Sample Output 1:
Dzeranov Iosif
Guev Timur
Petrov Petr
Sample Input 2:
4
Petrov Petr 3
Dzeranov Iosif 5
Guev Timur 4
Petrov2 Petr 6
Sample Output 2:
Petrov2 Petr
Dzeranov Iosif
Guev Timur
Сортировка простыми вставками
Проблема
Дана последовательность чисел, состоящая не более чем из 104 элементов.
Необходимо упорядочить числа по неубыванию.
Пример 1.
Входные данные:
4-10 11 8 6 10-5
Вы ходи ы е да иные:
-10-5 4 6 8 10 11
Пример 2.
входные данные:
10 8 2 8 б С 1
Выходные данные:
0 1 2 6 8 8 10
98 Алгоритмы сортировки данных
Идея сортировки вставками
Общая суть сортировки неганками такова.
1. Перебираются элементы в неотсортированной части массива. Вна-
чале отсортированная часть состоит только из первого элемента.
2. Каждый элемент вставляется в отсортированную часть массива на
то место, где он должен находиться.
То есть сортировка вставками всегда делит массив на 2 части — отсор
тированную и неотсортированную. Из неотсортированной части извлека-
ется любой элемент Поскольку другая часть массива отсортирована, то
в ней достаточно быстро можно найти свое место для этого извлеченного
элемента. Элемент вставляется куда нужно, в результате чего отсортиро-
ванная часть массива увеличивается, а неотсортированная уменьшается.
Так будет происходить до тех пор, пека набор входных данных не будет
исчерпан. Тогда элементы будут отсортированы.
Каждый из нас, независимо от рода деятельности, применял алгоритм
сортировки вставками, просто не осознавал это. Например, когда сорти
ровали купюры в кошельке — берем 100 рублей и смотрим — идут 10, 50
и 500-рублевые купюры. Вот как раз между 50 и 500 и вставляем нашу
сотню. Или, например, игра в карточного дурака. Когда мы тянем карту' из
колоды, мы смотрим на наши разложенные по возрастанию карты и в за-
висимости от достоинства вытянутой карты помещаем карту в соответ-
ствующее место.
Алгоритм
Пройдемся по массиву;
Запомним во временную переменную (назовем buffer) значение текущего
элемента массива;
Пока элементы слева от запомненного значения больше, чем запомнен-
ное, — перемещаем их на позицию вправо. Получается, что предыдущий
элемент займет ячейку запомненного. А тот, что стоит перед предыду-
щим, — переместится в свою очередь на место предыдущего. И так эле-
менты будут двигаться друг за дружкой.
Сортировка простыми вставками 99
Движение элементов заканчивается, если очередной элемент, который
нужно сдвинуть, оказывается по значению меньше, чем тот, что запомнили
во временную переменную в начале цикла.
Наглядный пример работы сортировки вставками
Пример работы алгоритма для массива 16 5 3 1 8 7 2 4]:
До После Описание шага
Первый проход (проталкиваем второй элемент —5)
|653 1 87 2 4] [563 1 87 2 4] Алгоритм сравнивает второй элемент с первым и меняет их местами
Второй проход (проталкиваем третий элемент — 3)
[563 1 87 2 4] [566 1 87 2 4] Сравнивает третий со вторым и второй элемент проталкивается вправо
|566 1 87 2 4] [356 1 87 2 4] Сравнивает 5 и 3, затем 5 проталкивается вправо. Элементы закончились, следовательно, 3 вставляется на 1 место
Третий проход (проталкиваем четвертый — V
[356 1 87 2 4] [356687 2 4] Сравнивает 6 и 1, затем 6 проталкивается вправо.
[35668 7 2 4] [355687 2 4] Сравнивает 5 и 1, затем 5 проталкивается вправо.
1355687 2 4] |1 3568 7 2 4] Сравнивает 3 и 1, затем 3 проталкивается вправо. Элементы закончились, следовательно, 1 вставляется на 1 место
Четвертый проход (проталкиваем пятый элемент — 8)
[135687 2 4] [1 35687 2 4] Сравнивает 6 и 8. Стоят в нужном порядке.
Пятый проход (приталкиваем шестой — 7)
|1 35687 2 4] [1 35688 2 4] Сравнивает 8 и 7, затем 8 проталкивается вправо.
|1 35688 2 4] [1 35678 2 4] Сравнивает 6 и 7. Не нужно проталкивать 7 вставляется в нужное место.
100 Алгоритмы сортировки данных
До После Описание шага
Шестой проход (проталкиваем седьмой — 2;
[1 356 78 2 4] [1 356 78 8 4] Сравнивает 8 и 2, затем 8 проталкивается вправо.
[1 35678 8 4] [1 35677 8 4] Сравнивает 7 и 2, затем 7 проталкивается вправо.
[1 3567 7 8 4] [1 35667 8 4] Сравнивает 6 и 2, затем 6 проталкивается вправо
[1 35667 8 4] [1 35567 8 4[ Сравнивает 5 и 2, затем 5 проталкивается вправо.
[1 3 5 5 6 7 8 4] [1 33567 8 4] Сравнивает 3 и 2, затем 3 проталкивается вправо
[1 3356 7 8 4] [1 2 3567 8 4] Сравнивает 1 и 2. Не нужно проталкивать. 2 вставляется в нужное место.
Седьмой проход (проталкиваем восьмой — 4)
[1 2 3 5 6 7 8 4| [1 2 356 7 8 8] Сравнивает 8 и 4, затем 8 проталкивается вправо.
Ц 23 567 8 8] [1 23567 7 8] Сравнивает 7 и 4, затем 7 проталкивается вправо.
Ц23567 7 8] [1 23566 7 8| Сравнивает 6 и 4, затем 6 проталкивается вправо.
[1 23566 7 8] [1 23556 7 8j Сравнивает 5 и 4, затем 5 проталкивается вправо.
11 23556 7 8] [1 23456 7 8] Сравнивает 3 и 4. Не нужно проталкиват ь. 4 вставляется в нужное место. Массив отсортирован!
Сортировка простыми вставками 101
Реализация
а
static void Insertionsort(intП array)
{
int buffer;
for (int i = 1; i < array.Length; i++)
{
buffer = arrayli]; // запоминаем в бубер элемент,
который нужно вставить на нужное место
int j = i; // индекс места, куда будем вставлять
buffer
// пока не дошли до начала массива и очередной
элемент больше буфера
while (j > 0 && array[j - 1] > buffer)
{
array[j] = array[j - 1]; // перемещаем больший
элемент на одну позицию вправо
j—; // передвигаем индекс для просмотра
элемента, который стоит левее
}
array[j] = buffer; // место найдено, вставить
элемент
}
Свойства алгоритма сортировки вставками
Свойство Ответ Комментарий
Устойчивость Да При равенстве элементов не происходит переупорядочиваиия элементов
Внутренняя/в! гешняя сортировка Внутренняя Нужно несколько раз пробегать по последовательности
Естественность поведения Да При частичном сортированном массиве алгоритм не будет ме- нять их относительный порядок и сработает быст рее обычного
102 Алгоритмы сортировки данных
Время работы
При анализе сортировки вставками стоит отметить, что, вне зависимости
от первоначального порядка элементов, для списка из п элементов будет
сделан л-1 проход.
Табличный анализ для сортировки вставками
Номер прохода по массиву Количество сравнений
1 1
2 2
3 3
...
л-1 л-1
Табличный анализ показывает число сравнений при каждом проходе. По-
считаем общее количество сравнений, то есть просуммируем все значе-
ния. Заметим, что данные числа представляют из себя арифметическую
последовательность, которую можем посчитать по формуле:
(первый элемент+последний элемект)-количесгво элементов
2
Подставим значения и получим:
(1 + (п - 1)) • (п - 1) _ п • (п - 1) _ п2 - п _ 1 2
2 “ 2 “ ~2~ ~2П
То есть, если убрать константы и слагаемые меньшей степени
асимптотическая сложность О(лг).
1
"2,:
, получится
Временная сложность Время работы Комментарий
В лучшем О(п) В лучшем случае, когда список уже отсортирован. Делаем 1 проход, чтобы убедиться, что данные упорядочены
В среднем О(л2) В среднем этот алгоритм требует п2 итераций цикла
В худшем О(л2) В лучшем случае, когда список уже отсортирован а обратном порядке, чем нужно
Сортировка простыми вставками 103
Применимость
Сортировка б стае ками наиболее эффективна, когда массив уже частич-
но отсортирован и когда элементов массива немного. Если же элементов
меньше 10, то данный алгоритм является лучшим. Во многих смешанных
сортировках используется алгоритм сортировки вставками как вспомога-
тельный. Можно привести пример с Array.Sort на С#.
Интересное для прочтения.
Преимущества и недостатки
Преимущества Недостатки
Прост в реализации Сложность по времени
Не требует дополнительной памяти Используется только на маленьких и средних последовательностях
На маленькой последовательности показывает лучшее время Алгоритм не умеет определято на промежуточном этапе, отсортирована ли последовательность
Задачи
Неубывание
Напишите программу, которая сортирует массив по неубыванию, с помо-
щью сортировки вставками.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
1000 — размер массива.
Во второй строке вводятся N целых чисел, каждое из которых по модулю
не превосходит 1000 — элементы массива.
Выходные данные
Вывести отсортированный по неубыванию массив на одной строке через
пробел.
104 Алгоритмы сортировки данных
Примечание:
Неубывание — это когда числа равны или возрастают
Sample Input 1:
5
15 1 5568 13
Sample Output 1:
1 5 13 15568
Sample Input 2:
1
1
Sample Output 2:
1
Sample Input 3:
2
3 1
Sample Output 3:
1 3
Невозрастание
Напишите программу, которая сортирует массив по невозрастанию, с по-
мощью сортировки вставками,
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
1000 — размер массива.
Во второй строке вводятся N целых чисел, каждое из которых по модулю
не превосходит 1000 — элементы массива.
выходные данные
Вывести отсортированный по невозрастанию массив на одной строке че-
рез пробел.
Сортировка простыми вставками 105
Примечание:
Невозрастание — это когда числа равны или убывают.
Sample Input 1;
5
15 1 5568 13
Sample Output 1:
568 15 13 5 1
Sample Input 2:
1
1
Sample Output 2:
1
Sample input 3:
2
3 1
Sample Output 3:
3 1
Вставка
Требуется вставить в данный массив на данное место данный элемент,
сдвинув остальные элементы вправо
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
i ООО — размер массива.
Во второй строке вводятся N целых чисел через пробел, каждое из кото-
рых по модулю не превосходит 1000 — элементы массива.
106 Алгоритмы сортировки данных
В третьей строке вводится число, которое необходимо вставить, и номер
места, на которое его нужно вставить. Числа разделяются одним пробе-
лом.
выходные данные
вывести получившийся массив.
Sample Input 1:
5
1 2 3 4 5
6 3
Sample Output 1:
1 2 6 3 4 5
Sample Input 2:
5
1 2 3 4 5
2 3
Sample Output 2:
1 2 2 3 4 5
Sample Input 3:
5
5 4 3 2 1
2 1
Sample Output 3:
2 5 4 3 2 1
Debug
Сделайте отладку работы метода сортировки вставками по возрастанию.
Для этого выведите состояние данного массива после каждой вставки на
отдельных строках. Если на очередном шаге элемент остался на своем ме-
Сортировка простыми вставками 107
сте, то выводить ничего не нужно. Если массив упорядочен изначально, то
ничего не следует выводить.
Входные данные
В первой строке задается одно натуральное число /V, не превосходящее
100 — размер массива.
Во второй строке вводятся /V натуральных чисел через пробел, каждое из
которых не превосходит 10? — элементы массива.
Выходные данные
Выведите строки (по количеству вставок) пс /V чисел каждая.
Sample Input 1:
4
4 13 2
Sample Output 1:
14 3 2
13 4 2
12 3 4
Sample Input 2:
2
2 1
Sample Output 2:
1 2
Sample Input 3:
4
2 15 3
Sample Output 3:
12 5 3
12 3 5
1 OF Алгоритмы сортирозки данных
Сортировка подсчетом
Проблема
Дана последовательность цифр, состоящая не более чем из К)12 элемен-
тов. Необходимо упорядочить цифры по неубыванию.
Пример 1.
Входные данные:
4 0 1 8 6 1 5
Выходные данные:
0 1 1 4 5 6 8
Пример 2.
Входные данные:
1 8 2 8 1 3 1
Выходные данные:
1 1 1 2 3 8 8
Сортировка подсчетом 109
Идея сортировки подсчетом
В этой задаче нужно отсортировать последовательность цифр, но слож-
ность ее в том, что последовательность содержит очень большое количе-
ство элементов (1012). Решить данную задачу теоретически возможно с ис-
пользованием алгоритма сортировки пузырьком, но по времени выполне-
ния данное решение не устроит, да и сохранить в массив 1012 элементов не
удастся. На помощь приходит сортировка подсчетом.
Дело в том, что диапазон возможных значений элементов пос ледователь-
ности ограничен, и поэтому вовсе не нужно хранить всю последователь-
ность в памяти, достаточно, считывая последовательность, поэлементно
вычислять для каждого возможного элемента х количество таких элемен-
тов в последовательности.
Для этого определяется некоторый массив counts, в котором каждый эле-
мент — это счетчик количества элементов исходной последовательности,
то есть в итоге в соплах] предполагаем получить количество элементов
последовательности, которые равны х. По завершении этого процесса до-
статочно вывести cwn£s[x] раз значение х в порядке увеличения х (по все-
му возможному диапазону).
Алгоритм
1. Создадим массив counts для подсчета значений. Размер данного
массива будет зависеть от ширины диапазона сортируемых чисел.
Б приведенной задаче ширина равна 10 (значения элементов от
0 до 9). Иначе говоря: ширина = максимальный элемент массиаа
+ 1.
2. Введем очередное число х.
3. Увеличим счетчик количества элементов, равных х: counf.s[x]=
cownte[x]+l.
4. После ввода всех чисел, обойдем массив counts, при этом для каж-
дого его / элемента выведем значение / столько раз. сколько он
встретился в исходном массиве. Индекс / при этом соответствует
значению числа исходного массива.
110 Алгоритмы сортировки данных
Реализация
Cfl
static void CounterSortO
{
int k = 1C; // ширина используемого диапазона
int[] counts = new int[k];
int n = Convert.Toint32(Console.ReadLine());
for (int i = 0; i < n; i++)
{
int x = Convert.Tolnt32(Console.ReadLine());
counts[x] = counts[x] + 1; // подсчитываем
}
for (int i = 0; i < k; i+ + )
{
for (int j = 0; j < counts[i]; j++) // counts[i]-
количество чисел i
{
Console.Write (i + « «);
}
}
}
Свойства алгоритма сортировки подсчетом
Свойство Ответ Комментарий
Устойчивость Нет Алгоритм не смотрит на взаимное расположение одинаковых элементов
Внутре княя/внешняя сортировка Внешняя Используется, когда размер входных данных велик. Обычно нельзя записать в массив такое количество данных.
Естественность поведения Нет Алгоритм не смотрит на взаимное расположение одинаковых элементов
Сортировка подсчетом 111
Время работы
При вводе всех элементов и при их подсчете потратим п операций. При про
ходе по нашему массиву counts сделаем к операций. И вывод отсортиро-
ванных элементов — п операций Итого: О(п + к + п) = О(2п + к) = О(п + к).
В данной сложности специально оставим к, чтобы понимать, от чего зави-
сит сложность алгоритма. Теоретически нужно убрать еще и к, так как он
меньше, чем п. Но я оставил, дабы понимать все происходящее.
Временная сложность Чремя работы Комментарий
Лучшее О(п+к) Алгоритм ведет себя одинаково при любых входных данных
В среднем О(п+к) Алгоритм ведет себя одинаково при любых входных данных
В худшем О(п+к) Алгоритм ведет себя одинаково при любых входных данных
Применимость
Применять его можно только для целых чисел, небольшого диапазона, так
как он требует О(к) дополнительной памяти, где к — ширина диапазона
сортируемых чисел. Алгоритм особо эффективен, когда сортируем боль-
шое количество чисел, значения которых имеют небольшой разброс —
например: массив из 1010 целых чисел, которые принимают значения от
О до 10ОО. То есть разница между количеством чисел и шириной диапазона
чисел должна быть существенная.
112 Алгоритмы сортировки данных
Преимущества и недостатки
Преимущества Недостатки
Прос1 в реализации Требует дополнительной памяти
Сложность по времени Используется только на маленьком диапазоне чисел
Сравнение на равенство Используется только для целых чисел
Используется на большом массиве данных с маленьким диапазоном чисел Алгоритм НЕ умеет определять на промежуточном этапе, отсортирована ли последовательность
Задачи
Невозрастание
Напишите программу, которая сортирует массив по невозрастанию с по-
мощью сортировки подсчетом.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
100 000 — размер массива.
Во второй строке вводятся W целых неотрицательных чисел, каждое из
которых не превосходит 1000.
Выходные данные
Вывести отсортированный по невозрастанию массив на одной строке че-
рез пробел.
Примечание:
Невозрастание — это когда числа равны или убывают.
Sample Input 1:
5
15 1 5568 13
Сортировка подсчетом 113
Sample Output 1:
568 15 13 5 1
Sample Input 2:
2
1 2
Sample Output 2:
2 1
Sample Input 3:
2
2 1
Sample Output 3:
2 1
1
На вход программы поступает последовательность из N целых положи-
тельных чисел. Все числа не превышают 10 ОСО. Выведите количество чи-
сел, которые встречаются ровно 2 раза.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
100 000.
В каждой из последующих /V строк записано одно целое положительное
число, не превышающее 1000.
Выходные данные
В качестве результата программа должна вывести количество чисел, кото-
рые встречаются ровно 2 раза.
Sample Input 1;
5
114 Алгоритмы сортировки данных
1
2
3
2
1
|3lujjjjJjj/1л43 D
uiiiuuw^iuauaji- J2UJ JKJ ГНУ
Sample Oulput 1:
2
Sample Input 2:
1
1000
Sample Output 2:
0
Sample Input 3:
1
1
Sample Output 3:
0
2
На вход программы поступает последовательность из N целых положи-
тельных чисел. Все числа не превышают 10 000. Найдите число, которое
встречается чаще всего. Если таких чисел несколько, выведите наиболь-
шее из них.
Входные данные
В первой строке входных данных задается количество чисел 7V(1 £ /VC 10е).
В каждой из последующих N строк записано одно целое положительное
число, не превышающее 10 000.
Выходные данные
В качестве результата программа должна вывести чис ло, которое встреча-
ется чаще всего. Если таких чисел несколько, выведите наибольшее из них.
Сортировка подсчетом 115
Sample Input 1:
5
1
2
3
4
2
Sample Output 1:
2
Sample Input 2:
5
1
2
3
4
5
Sample Output 2:
5
3
На вход программы поступает последовательность из N целых положи-
тельных чисел. Все числа не превышают 100. Найдите число, которое
встречается реже всего. Если таких чисел несколько, выведите наимень-
шее из них.
Входные данные
В первой строке входных данных задается количество чисел /V(l < N < 10s).
3 каждой из последующих N строк записано одно целое положительное
число, не превышающее 100
Выходные данные
В качестве результата программа должна вывести число, которое встре-
чается реже всего. Если таких чисел несколько, выведите наименьшее из
них.
116 Алгоритм! >i сортировки данных
Sample Input 1:
5
1
5
5
5
5
Sample Output 1:
1
Sample Input 2:
5
2
5
5
5
5
Sample Output 2:
2
Sample Input 3:
5
100
5
5
5
5
Sample Output 3:
100
Sample Input 4:
5
5
4
3
Сортире вка подсчетом 117
4
5
Sample Output 4:
3
Дан набор из N положительных целых чисел. Для каждого числа вычисля-
ется сумма цифр его десятичной записи. Необходимо определить, какая
сумма цифр чаще всего встречается у чисел этого набора. Если таких сумм
несколько, нужно вывести наименьшую из них.
Входные данные
В первой строке входных данных задается количество чисел Л/(1 С N < 106).
В каждой из последующих N строк записано одно целое положительное
число, не превышающее 10 000.
Выходные данные
В качестве результата программа должна вывести сумму цифр числа, ко-
торая встречается чаще всего. Если таких сумм несколько, нужно вывести
наименьшую из них.
Sample Input:
3
124
234
12
Sample Output:
3
118 Алгоритмы сортировки данных
5
Назовем длиной числа количество цифр в его десятичной записи. Напри-
мер, длина числа 2019 равна 4, а длина числа 25 равна 2.
Дан набор из N целых положительных чисел, каждое из которых меньше
108.1 'юобходимо определить, числа какой длины реже всего (но не менее
одного раза) встречаются в данном наборе и сколько в нем чисел этой дли-
ны. Если числа разной длины встречаются одинаково часто (и реже, чем
числа любой другой длины), нужно выбрать меньшую длину. Напишите эф
фективную по времени и но памяти программу для решения этой задачи.
Входные данные
В первой строке входных данных задается количество чисел N(1 С N <
1000).
В каждой из последующих W строк записано одно целое положительное
число, меньшее 108.
Выходные данные
Необходимо определить, числа какой длины реже всего (ко не менее од-
ного раза) встречаются в данном наборе и сколько в нем чисел этой длины.
Если числа разной длины встречаются одинаково часто (и реже, чем числа
любой другой длины), нужно выбрать меньшую длину.
Пояснения к примеру:
В данном наборе реже всего (по 1 разу) встречаются числа длины 2 и 4.
Выбираем меньшую длину, выводим саму длину (2) и количество чисел
этой длины (1).
Sample Input 1:
5
25
147
115
327
1Э00
Сортировка подсчетом 119
Sample Output 1:
2 1
Sample Input 2:
1
10
Sample Output 2:
2 1
Sample Input 3:
1
1
Sample Output 3:
1 1
Лучшие
В 39 школе в 7 -м «Б» классе учатся /V учеников. Недавно они писали прове-
рочную работу по информатике. Определите трех учеников с наилучшими
баллами. Выведи те фамилии и имена этих учащихся в порядке убывания
их баллов. Известно, что у всех учеников разные баллы.
входные данные
На первой строке дано число N(3^ N 000 000) — количество учеников.
В следующих Л; строках заданы фамилия, имя и балл по информатике.
Данные в каждой из строк разделены одним пробелом. Балл — это целое
значение от 1 до 10ОО ООО.
Выходные данные
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фа-
милию и имя одним пробелом. Выводить оценки не нужно.
Примечание: используете сортировку подсчетом.
120 Алгоритмы сортировки данных
Sample Input 1:
3
Petrov Petr 3
Dzeranov Iosif 5
Guev Timur 4
Sample Output 1:
Dzeranov Iosif
Guev Timur
Petrov Petr
Sample Input 2:
4
Petrov Petr 3
Dzeranov Iosif 5
Guev Timur 4
Petrov2 Petr 6
Sample Output 2:
Petrov2 Petr
Dzeranov Iosif
Guev Timur
Анализ текста
На вход программе подаются Л/ строк, каждая из которых содержит ан-
глийские слова. В одной строке может быть произвольное количество
слов. Все слова записаны строчными (маленькими) английскими буквами.
Между словами в строке может быть один или больше пробелов, возмож-
ны пробелы в начале и в конце строки. Других символов, кроме строчных
английских букв и пробелов, в строках нет.
Напишите программу, которая будет определять количество слов, начи-
нающихся на каждую букву английского алфавита. Затем выведите буквы
в алфавитном порядке с данным количеством.
Сортировка подсчетом 121
Входные данные
В первой строке входных данных задается 7V( 1 < /V <160).
В каждой из последующих Л’ строк записана строка, состоящая из строч-
ных английских букв и пробелов, которая не превышает 200 символов.
Выходные данные
Найдите количество слов, начинающихся на каждую букву английского
алфавита. Затем выведите буквы в алфавитном порядке с данным количе-
ством через пробел. Если на какую-то букву слов нет, выводить эту букву
не надо.
Примечание: Английский алфавит совпадает с латинским и содержит
26 букв от а до z:
Sample Input:
3
dzerancv guev
icsif timur
i bee geek d
Sample Output:
b
d
g
i
t
1
2
2
2
1
Обобщение на произвольный
целочисленный диапазон
Возникает несколько вопросов.
1. Что делать, если диапазон значений (min и max) заранее не изве-
стен? Это можно решить линейным поиском min и max, что не по-
влияет на асимптотику алгоритма.
122 Алгоритмы сортировки ла! <ных
2. Что делать, если минимальное значение больше нуля? Можно, ко-
нечно, ничего не менять, но для экономии памяти сделаем следую-
щее: при работе с массивом counts из очередного числа вычитать
min, а при получении или выводе элементов обратно прибавлять
min. Тогда размерность массива counts равна тах-min+l.
3. Что делать, если в сортируемых данных присутствуют отрица-
тельные числа? Мы знаем, ч то отрицательных индексов не бывает.
Тогда давайте превратим все элементы в неотрицательные числа,
то есть ко всем элементам массива прибавим \min\ (модуль ми-
нимального числа), а при получении или выводе элементов будем
обратно вычитать \min\. Тогда размерность массива counts равна
max-min+1.
Клавиатура
Всем известно, что со временем клавиатура изнашивается, и клавиши на
ней начинают залипать. Конечно, некоторое время такую клавиатуру еще
можно использовать, но для нажатий клавиш приходится использовать
большую силу.
При изготовлении клавиату-
ры изначально для каждой
клавиши задается количество
нажатий, которое она должна
выдерживать. Если знать эти
величины для используемой
клавиатуры, то для опреде-
ленной последовательно-
сти нажатых клавиш можно
определить, какие клавиши
в процессе их использования
сломаются, а какие — нет.
Требуется написать програм-
му, определяющую, какие
клавиши сломаются в про-
цессе заданного варианта
эксплуатации клавиатуры.
Сортирогка подсчетом 123
Входные данные
Первая строка входного файла содержит натуральное число /V(l С /V
С 100) — количество клавиш на клавиатуре.
Вторая строка содержит N натуральных чисел — С,,С2,..., где С.(1 < Ct
<100 000) — количество нажатий, выдерживаемых Ай клавишей.
Третья строка содержит натуральное число К (1 О < 100000) — общее
количество нажатий клавиш.
Четвертая строка содержит К натуральных чисел А.(1 С Р /V) — последо-
вательность нажатых клавиш.
Выходные данные
Выведите N строк, содержащих информацию об исправности клавиш.
Если Ая клавиша сломалась, то Ая строка должна содержать слово yes (без
кавычек), если же клавиша работоспособна — слово по.
Sample Input 1:
5
2 10 1 5 2
10
2234311225
Sample Output 1:
no
no
yes
no
no
Sample Input 2:
5
1 50 3 4 3
16
1234513345555545
124 Адгрритмы сортировки данных
Sample Output 2:
yes
no
no
no
yes
Есть платформа, состоящая из N колонок. Квадраты размера 1x1 появля-
ются один за другим в некоторых колонках на платформе. Если в колонке
нет квадратов, то квадрат появляется в нижнем ряду. Иначе же квадрат
появляется сверху от самого высокого квадрата в этой колонке
Когда в каждой из N колонок есть хотя бы один квадрат, нижний ряд удаля-
ется. За это вы получаете 1 очко, а все остальные квадраты падают на один
ряд вниз.
Ваша задача — посчитать количество очков, которое вы получите.
Входные данные
Первая строка содержит два целых числа N и М (1 €'V, 1 000) — количе-
ство колонок на платформе и количество квадратов.
Сортировка подсчетом 125
В следующей строке содержится М целых чисел Cl, С2... CM(I^CKN') —
колонка, в которой появляется лй квадрат.
Выходные данные
Выведите единственное целое число — количество очков, которое вы по-
лучите.
Примечание
В примере ответ будет равен 2, потому что после появления 6-го квадрата
будет удален один ряд (количество квадратов на платформе будет выгля-
деть как 12 3 1 ], и после удаления одного ряда как [1 2 0]).
После появления 8-го квадрата количества будут выглядеть как [2 2 1],
и после удаления одного ряда как [1 10].
Следовательно, ответ будет равен 2
Sample Input 1:
3 8
11222313
Sample Output 1:
2
Sample Input 2:
3 9
112223123
Sample Output 2.
2
126 А лгоритмы сорт иривки данных
Джон
Джон очень веселый парень. Он постоянно играется, но только сам с со-
бой. А еще он недавно заказал штаны с большим количеством карманов,
чтобы носить с собой много монет.
У Джона есть N монет При этом достоинство /-й монеты равно AL Джон
хочет распределить монеты по своим карманам, но он не может класть две
монеты одинакового достоинства в один и тот же карман.
Например, если у Джона есть шесть монет, представленных в виде массива
А=[5,6,4,7,7,6], он может распределить их по двум карманам следующим
образом: [5,6,7],[4,7,6].
Джон хочет распределить все имеющиеся у него монеты, используя мини-
мально возможное количество кармансч. Помогите ему сделать это.
Входные данные
Первая строка входных данных содержит одно целое число /V (1 <Л<100)—
количество монет.
Вторая строка входных данных содержит N целых чисел А1, А2,. , AN (1
<100) — достоинства монет.
Сортировка подсчетом 127
Выходные данные
Выведите о дю целое число — минимальное возможное количество карма-
нов, необходимое Джону, чтобы распределить все имеющиеся у него мо
негы таким образом, что никакие две монеты с одинаковым достоинством
не лежат в одном и том же кармане
Sample Input:
б
5 6 4 7 7 6
Sample Output:
2
Числа-анаграммы
Число называется анаграммой другого числа, если оно может быть полу-
чено любой перестановкой его цифр.
Входные данные
Даны два натуральных числа на отдельных строках. Каждое из чисел не
превышает Ю9
Выходные данные
Требуется вывести YES — если введенные числа являются анаграммами
друг друга, NO — если нет.
Sample Input 1:
524
452
Sample Output 1:
YES
Sample Input 2:
554
452
Sample Output 2:
NO
128 Алгоритмы сортировки данных
Слова-анаграммы
Слово называется анаграммой другого слова, если оно может быть полу-
чено перестановкой его символов
Входные данные
Даны два слова на отдельных строках. Слова состоят из строчных латин-
ских букв. Длины слов не превышают 255.
Выходные данные
Требуется вывести YES - если введенные слова являются анаграммами
друг друга, NO — если нет.
Sample Input 1:
slovo
volos
Sample Output 1:
YES
Sample Input 2:
book
koab
Sample Output 2:
NO
Сортировка подсчетом 129
Разброс (*)
Дано Л/ целых чисел, которые требуется отсортировать в порядке неубыва-
ния. В связи с нормами BeeGeek среди чисел не будет двух, разница между
которыми превышает 1С7
Входные данные
Первая строка входного файла содержит целое число Л/(1< ЛЧ 105).
Вторая строка содержит N целых чисел, каждое из которых не превышает
по модулю 2 109. Никакие два не различаются более, чем на 107.
Выходные данные
Выведите данные числа в порядке неубывания.
Sample Input:
б
1С0207 157102 200154
Sample Output:
100102 154157 200207
Палиндром (*)
Палиндром — это строка, которая читается одинаково как справа налево,
так и слева направо
На вход программы поступает набор заглавных латинских букв. Разреша-
ется переставлять буквы, а также удалять некоторые буквы. Требуется из
данных букв по указанным правилам составить палиндром наибольшей
длины, а если таких палиндромов несколько, то выбрать первый из них
в алфавитном порядке.
Входные данные
В первой строке входных данных содержится число N (Ч ЛЧ1С5).
130 Алгоритмы сортировки данных
Во второй строке задается последовательность из N заглавных латинских
букв (буквы записаны без пробелов).
Выходные данные
В единственной строке выходных данных выведите искомый палиндром.
Sample Input 1:
4
АВ АВ
Sample Output 1:
ABBA
Sample Input 2:
5
AABCD
Sample Output 2:
ABA
Поразрядная сортировка
Проблема
Дана последовательность положительных чисел, состоящая не более чем
из 107 элементов. Числа могут принимать значения до 1 О’. Необходимо
упорядочить числа по неубыванию.
Пример.
Входные данные:
4354 105091563 16 31 51000С
Выходные данные:
5 10 16 31568 4354509110000
Поразрядная сортировка 131
Идея поразрядной сортировки
В этой задаче нужно отсортировать последовательность чисел, но слож-
ность ее в том. что последовательность содержит большое количество
элементов (107). Решить данную задачу теоретически возможно с исполь-
зованием изученных алгоритмов сортировки на основе сравнений, но по
времени выполнения данное решение не устроит. Вы могли бы решить, что
сортировка подсчетом могла бы тоже подойти, но сами числа находятся
в большом диапазоне (109), и хранить такой массив просто не позволи-
тельно. На помощь приходи! поразрядная сортировка.
Идея следующая: двигаемся о г младших разрядов к старшим и на каждой
итерации распределяем элементы массива в зависимости от того, какая
цифра содержится в разряде (методом подсчета). После очередного рас-
пределения мы возвращаем элементы в основной массив в том порядке,
в котором элементы попали в классы при очередном перераспределении.
Для поразрядных сортировок важно, чтобы элементы рассматривались
как имеющие одинаковое количество разрядо в. Если фактически количе-
ство разрядов отличается, то проблема решается припиской дополнитель-
ных нулей в качестве старших разрядов.
Примечание: также можно двигаться от старших разрядов к младшим раз-
рядам.
Алгоритм
1. Повторить по числу разрядов.
1. сгруппировать числа по текущему разряду;
2. выписать их в порядке увеличения значения разряда;
132 Алгоритмы сортировки данных
Реализация
с#
static void RadixSort(int[] array)
{
int digitCounts = 10; // количество различных цифр
int maxLengthOfNumber = 9; // максимальная длина числа
int р = 1; // степень 10. Нужна для получения
очередного разряда
List<int>[] pocket = new List<int>[digitCcunts] ;
// массив для распределения элементов по «корзинам»
for (int i = 0; i < pocket.Length; i++)
pocket[i] = new List<int>();
for (int i = 0; i < maxLengthOfNumber; i++)
Il проходимся по разрядам
{
for (int j =0; j < array.Length; j++)
// проходимся по числам
{
int index = arraytj] / P % 1C; // находим
индекс корзины
pocket[index].Aod(array[j]); // добавляем
}
int count =0; //на каком месте вставляем
в первоначальном массиве
for (int j = 0; j < digitcounts ; j++)
// проходимся но корзинам
{
for (int k = 0; k < pocket[j]-Count; k++)
/7 проходимся по элементам очередной корзины
{
array[count] = pocket[j][k];
// перебрасываем обратно в первоначальный массив
count++; // увеличиваем место вставки
элемента в первоначальном массиве
}
pocket[j].Clear(); // очищаем корзину
}
р *= 10; // получаем следующую степень
}
}
Поразрядная сс ртировка 133
Свойства алгоритма поразрядной сортировки
Свойство Ответ Комментарий
Устойчивость Да Алгоритм сохраняет взаимное расположение одинаковых элементов — в каком порядке были добавлены элементы в корзины, в таком порядке и вынуты.
Внутренняя/внешняя сортировка Внутренняя Все элементы проходят сортировки ио разрядам.
Естественность поведения Нет Алгоритм не может определить частично отсортированные данные.
Время работы
Для каждого разряда числа идет разбиение чисел по корзинам (л опе-
раций), а затем обратный переброс элементов (л операций). Итого:
О(£/-(л+л))=О(с/-л), где d — количество разрядов. В данной сложности
специально оставим d, чтобы понимать, от чего зависит сложность алго-
ритма. Теоретически нужно убрать еще и d, так как он значительно меньше,
чем л, а чаще всего это 10. Но я оставил, дабы понимать все происходящее.
134 Алгоритмы сортировки данных
Временная сложность Время работы Комментарий
Лучшее O(d-n) Алгоритм ведет себя одинаково при любых входных данных
В среднем O(dn) Алгоритм ведет себя одинаково при любых входных данных
В худшем O(d-n) Алгоритм ведет себя одинаково при любых входных данных
Применимость
Алгоритм особо эффективен, когда сортируем среднее или маленькое ко-
личество чисел, значения которых могут быть сколько угодно большими —
например1 массив из 107 целых чисел, которые принимают значения от
О доЮ10. То есть разница между количеством чисел и шириной диапазона
чисел должна быть существенная, в пользу ширины диапазона чисел.
Преимущества и недостатки
Преимущества Недостатки
Сложность по времени Не прост и реализации
Сравнение на равенство Требует дополнительной памяти
Используется для сколько угодно больших чисел Используется только на маленьком и среднем количестве чисел
Используется только для целых чисел
Алгоритм НЕ умеет определять на промежуточном этапе, отсортирована ли последовательность
Поразрядная сортировка 1 35
Задачи
Невозрастание
Напишите программу, которая сортирует массив по невозрастанию с по-
мощью поразрядной сортировки.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее
100 000 — размер массива.
Во второй строке вводятся N целых неотрицательных чисел, каждое из
которых не превосходит 1000.
Выходные данные
Вывести отсортированный по невозрастанию массив на одной строке че-
рез пробел.
Примечание:
Невозрастание — это когда числа равны или убывают’.
Sample Input:
5
15 1 5568 13
Sample Output:
568 15 13 5 1
Алфавит
Напишите программу, которая сортирует список слов в алфавитном по-
рядке.
Входные данные
В первой строке вводится количество слов N (1 < N С 100000).
В следующих N строках вводятся слова, по одному в строке. Слова состоят
из маленьких лагинских букв. Длина строки не превышает 100.
136 Алгоритмы со ртировки данных
Выходные данные
Программа должна вывести список слов, отсортированный по алфавиту.
Sample Input:
5
abc
ab
acb
b
abacaba
Sample Output:
ab
abacaba
abc
ac.b
b
Сравнение алгоритмов сортировки 137
Сравнение алгоритмов сортировки
• Пузырьковая сортировка умеет определять на промежуточном
этапе, отсортирована ли последовательность.
• Сортировка выбором минимизирует количество обменов.
• Сортировка вставками на маленьких входных данных работает эф -
фективнее других алгоритмов сортировки.
• Поразрядная сортировка особо эффективна, когда последователь-
ность содержит среднее или маленькое количество чисел, значе-
ния которых могут быть сколько угодно большими.
• Временная сложность пузырьковой сортировки, сортировки выбо-
ром и сортировки вставками — О(л2). Сортировка подсчетом и по-
разрядная сортировка имеют временную сложность О(п).
• Сортировка подсчетом и поразрядная сортировка выполняют
сравнение на равенство, а пузырьковая сортировка, сортировка
выбором и сортировка вставками выполняют сравнение на основе
порядка.
Пузырьковая сортировка Сортировка зыбором Сортировка вставками Сортировка подсчетом Поразрядная сортировка
Устойчивый да нет да нет да
Внешняя/ внутренняя внутренняя внутренняя внутренняя внешняя внутренняя
Естественность поведения да нет да нет нет
Сравнение порядок порядок порядок равенстве равенство
Временная сложность О(п2) О(л2) О(п2) О(п) О(п)
138 Алгоритмы сортировки дан ных
Выбор алгоритма сортировки
Сравнение алгоритмов сортировки 139
Заключение
Ура! Вы справились с алгоритмами!
Спасибо, что дочитали до конца эту книгу. Теперь вы знаете, как анализи-
ровать алгоритмы, знакомы с алгоритмами поиска и сортировки.
Отзывы от учеников, прошедших курс, можно посмотреть по
Д ссылке (https://stepik.org/course/23981/reviews)
Если вы захотите оставить свое мнение о курсе, поделиться иде-
ями или задать вопросы — пишите на адрес электронной почты
iodzeranov@mail.ru или в Telegram.
Буду рад обратной связи!
Желаю успехов!
f рекомендует
Математика для безнадежных гуманитариев
Литвак Н. В., Кечеджан А. Г.
ISBN 978-5-17-161635-9
Если вы убеждены в существовании особых
математических способностей или считаете
слово «гуманитарий» оскорблением, вы попа-
ли в ловушку устаревших стереотипов. Про-
фессор математики, лауреат премии «Просве
титель» Нелли Литвак и креативный продюсер
Алла Кечеджан не только докажут вам, что
математика доступна абсолютно всем, но и на-
учат смотреть на мир через призму этой науки.
Если вы считаете себя гуманитарием, вы узна-
ете, какие математические законы связывают
паркет на полу комнаты с вращением спутника
и биением сердца.
Если вы считаете себя математиком, вы узна-
ете, как избежать систематической ошибки
выжившего, а '/же известные положения науки
предстанут перед вами в новом свете.
Нелли Литьак
Алла Кечеджан
БЕЗНАДЕЖНЫ X V
ГУМАНИТАРИЕВ
\ Юлой. он. сальш
.луиишй способ
понаппб jwawe/tafnuity?
Зачел дэгменатинад
ICO SCO joiw^ah'iext.cmC
rneopew nu>patopa?;.
b „................. ।
Форели?
Оглавление
05 авторе............................................... 3
Кому адресована эта книга................................. .5
Как читать эту книгу..................................... .6
Благодарности...............................................7
Анализ алгоритмов......... ... .............................8
Асимптотический анализ..... ..............................8
Расчет временной сложности...............................10
Теория алгоритмов...................................... 12
Расчет временной сложности на практике...................17
Расчет сложности по памяти .. .......................... 19
Выводы...................................................20
Алгоритмы поиска...........................................21
Общая информация о поиске... . ..........................21
Линейный поиск...........................................23
Проблема..............................................23
Идея решения....................................... 23
Суть алгоритма линейного поиска.................... 23
Алгоритм..............................................25
Реализация.......................................... . 25
Время работы........................................ 25
Преимущества и недостатки.............................26
Применимость.. ...................................... 26
Задачи................................................27
Бинарный поиск........................................ 35
Оглавление 141
Проблема............................................... 35
Идея алгоритма бинарного (двоичного) поиска (Binary search)... .36
Суть алгоритма бинарного поиска........................36
Алгоритм............................................... 36
Отладка................................................ 37
Реализация.............................................37
Время работы...........................................39
Преимущества и недостатки..............................41
Применимость.......................................... 41
Распространенные ошибки................................41
Реальные примеры использования.................... .41
Задачи.................................................42
Модификации бинарного поиска..............................45
Нахождение самого левого вхождения.....................46
Реализация.............................................47
Нахождение самого правого вхождения....................47
Реализация. ............................................49
Задачи.................................................49
Поиск прыжками (Jump search)..............................57
Проблема ........................................ . . .57
Суть алгоритма поиска прыжками (Jump search)..... . . .59
Алгоритм...............................................59
Реализация. . . .......................................59
Время работы ..........................................61
Применимость.......................................... 61
Преимущества и недостатки.......................... 61
Задачи.................................................62
Модификации поиска прыжками (Jump search).................64
Нахождение самого левого вхождения.....................64
Реализация. ............................... . .........64
Нахождение самого правого вхождения....................66
Реализация... .........................................67
Задачи .. 68
142 Оглавление
Сравнение алгоритмов поиска...............................71
Важные различия........................................72
Выбор алгоритма поиска....................................73
Алгоритмы сортировки данных.................................75
Общая информация о сортировках............................75
Свойства алгоритмов сортировки............................77
Сортировка пузырьком........ .............................78
Проблема...............................................78
Идея сортировки пузырьком (Bubble Sort)................79
Алгоритм...............................................79
Наглядный пример..................................... . .79
Реализация.............................................81
Реализация с оптимизацией..............................81
Свойства алгоритма сортировки пузырьком................82
Время работы......................................... . .83
Табличный анализ для сортировки пузырьком..............83
Применимость........................... .. .......... 84
Преимущества и недостатки..............................84
Задачи.................................................85
Сортировка выбором........................................90
Проблема............................................. . .90
Идея сортировки выбором................................90
Алгоритм...............................................91
Наглядный пример с пошаговым разбором..................91
Реализация.............................................92
Свойства алгоритма сортировки выбором..................93
Время работы...........................................93
Табличный анализ для сортировки выбором................93
Применимость......................................... . .94
Преимущества и недостатки..............................94
Задачи.................................................95
Сортировка простыми вставками.............................97
Проблема...............................................97
Оглавление 143
Идея сортировки вставками..............................98
Алгоритм...............................................98
Наглядный пример работы сортировки вставками ... ......99
Реализация........................................... 101
Свойства алгоритма сортировки вставками.............. 101
Время работы..........................................102
Применимость......................................... 103
Преимущества и недостатки............................ 103
Задачи............................................... 103
Сортировка подсчетом.................................... 108
Идея сортировки подсчетом.............................109
Алгоритм..............................................109
Реализация............................................110
Свойства алгоритма сортировки подсчетом...............110
Время работы......................................... 111
Применимость....... ................................. 111
Преимущества и недостатки.............................112
Задачи................................................112
Обобщение на произвольный целочисленный диапазон......121
Поразрядная сортировка...................................130
Проблема..............................................130
Идея поразрядной сортировки...........................131
Алгоритм... ..........................................131
Реализация............................................132
Свойства алгоритма поразрядной сортировки.............133
Время работы ........................................ 133
Применимость..........................................134
Преимущества и недостатки. ...........................134
Задачи................................................135
Сравнение алгоритмов сортировки......................... 137
Выбор алгоритма сортировки.............................. 138
Заключение................................................ 139
Издание для долог нательного образования
Для широкого круга читателей
Дзерачов Иосиф Витальевич
АЛГОРИТМЫ ПОИСКА И СОРТИРОВКИ
Ответственный редап-ор В Софронов
Менеджер проекта М. Канохина
Дизайн обложки А. хайрушева
Иллюстрации £. Лаврушечкина
Компьютерная верстка И Гоишин
Корректор т. Дек чрева
Страна происхождения: Российская Федерация
Шыгарущы ел: Ресей Федераоиясы
Изготовитель: ООО «Издательство АСТ»
129085, Российская Федерация.". Москна. Звездный бульвар, д. 21 стр. 1,
комн. 705, пом. I, этаж 7
Наш сайг www.ast .ru e-mail ask^ast'u
Адрес места осуществления деятельности по изготовлению продукции'
123112, Москва, пресненская наб.«в. 6 сто. 2, Деловой комплекс «империя». 14,1ьэтаж.
Общероссийский класои фикатор продукции QK-034 2014 (КПЕС 2008),
5а 11.1 - книги, брси-юры леча, ные; ГР ТС 007/2011
«Сасса Дет» ЖШК
129085, Мескеу к., Звёздный гулзар, 21-уй, 1-курылыс, 705-белме I жай, 7-кабат
Онд1р1с орныны н мекен жайы: 123112. Маскеу каласы, Пресненская жагалауы,
6-уй, 2-курылыс «Империя»бизнескешен!, 14 15кабат.
Б|зд(н эгек'рондыкмекенжаймнз' www ast.ru
Интернет дукен. wwA.bock24.kz
Импортер в “есиублику Казахстан ТОО «РДЦ-Алматы».
Казахстан Республикасьндагы импорттаушы «РДЦ-Алматы» Ж11С
Дистрибьютор и представитель го приему претензий на продукцию s Республике Казахстан:
ТОО«РДЦ-Алмазы» Казаксаг ^еспублихасында дистрь бькгор жа не чн!н бойынша арыз-талаптарды
KaObafla'iob»ttJheKm:-«PflU Алматы» ЖШС Алматы к Домбровский кеи . 3«г»уй, Ь литер, 1 хецсе
1ел.: 8 (/27) 251 5990,91. Факс: 8 (727) 251 b992iuiKi 107;
E-mail: ROC-Almaty@eksmo.kz, www.boci<24 kz
Tayap белпй: «ACT»
внд|рген мемлекеп Ресей
Сертификация карастырылмаган
11одпйсано в печать 03.1 п 2025. Формат 70х 100’/,..
гарнитура Adonis. Печать офсетная. Уол. теч л 11,67.
Тираж. 2000 экз. Заказ 7232.
Отпечатано с готовых файлов заказчика
в АО «Первая Образцовая типография»,
филиал «УЛЬЯНОВСКИЙ ДОМ ПЕЧАТИ»
432980, Россия, г. Ульяновск, ул. Гончарова, 14
ISBN 978-5-17-169830-0
Эта книга написана опытным программистом
(Сбербанк, Mail.ru) и преподавателем Иосифом
Дзерановым.
В ней вы найдете секреты успешного освоения
алгоритмов - ключевой части карьеры разработчика.
Изучив алгоритмы поиска и сортировки, вы сможете
лучше понимать эффективность кода и подготовитесь
к реальным задачам и собеседованиям.
Каждый урок - это шаг в мир алгоритмов, где
вы научитесь анализировать данные, выбирать
оптимальные методы и применять их на практике.
Раскройте свой профессиональный потенциал!
Ищите школу Иосифа в социальных сетях: Iron
Programmer
книги для любого настроения здесь
ИЗДАТЕЛЬСКАЯ ГРУППА ACT
www.ast.ru | www.book24.ru
” vk.com dzdatelstvoast
В ok.ru/izdatelstvuast
IRON PROGRAMMER
9 785171 698300 >