Программирование на учи ру большая сортировка ответы

Задача сортировки состоит в том. Чтобы переставить набор элементов в порядке возрастания. Одна из причин, по которой он так полезен, заключается в том. Что гораздо проще искать что-то в отсортированном списке. Чем в несортированном. В этом разделе мы подробно рассмотрим два классических алгоритма сортировки и поиска. А также несколько приложений. Где их эффективность играет решающую роль.


Бинарный поиск

Поиск скрытого числа с помощью двоичного поиска

В игре n целых чисел между 0 и n-1. (Для простоты будем считать. Что n — это степень двух.) Каждый раз. Когда вы делаете предположение. Вам говорят. Является ли ваша догадка слишком высокой или слишком низкой.

Эффективная стратегия состоит в том , чтобы поддерживать интервал [lo, hi), который содержит скрытое число. Угадать число в середине интервала. А затем использовать ответ. Чтобы вдвое уменьшить размер интервала. Программа questions.py реализует эту стратегию. Которая является примером общего метода решения проблем. Известного как бинарный поиск.

Доказательство правильности.

Во — первых, мы должны убедить себя, что этот подход верен: он всегда ведет нас к скрытому числу. Мы делаем это путем установления следующих фактов:

  • Интервал всегда содержит скрытое число.
  • Размеры интервалов-это степени двойки, уменьшающиеся от

    n.

Первый из этих фактов подкрепляется кодом; второй следует, отмечая, что если размер интервала (hilo) является степенью двойки, то следующий размер интервала равен (hilo)/2, что является следующей меньшей степенью двойки. Эти факты лежат в основе индукционного доказательства того, что метод работает так, как задумано. В конце концов размер интервала становится равным 1, так что мы гарантированно найдем это число.

Анализ времени выполнения.

Поскольку размер интервала уменьшается в 2 раза на каждой итерации (а базовый случай достигается при

n = 1), время выполнения двоичного поиска равно lg n.

Линейно-логарифмическая пропасть.

Альтернативой двоичному поиску является угадывание 0, затем 1, затем 2, затем 3 и так далее. Пока не попадет в скрытое число. Мы называем такой алгоритм алгоритмом грубой силы: он, кажется, выполняет работу. Но без особого учета стоимости (что может помешать ему фактически выполнить работу для больших проблем). В этом случае время работы алгоритма грубой силы чувствительно к входному значению, но может быть равно n и имеет ожидаемое значение n/2, если входное значение выбрано случайным образом. Между тем, бинарный поиск гарантированно использует не более lg

n шагов.

Двоичное представление.

Если оглянуться назад binary.py, вы узнаете, что двоичный поиск-это почти то же самое вычисление. Что и преобразование числа в двоичное! Каждая догадка определяет один бит ответа. В нашем примере информация о том. Что число находится между 0 и 127, говорит о том. Что число битов в его двоичном представлении равно 7, ответ на первый вопрос (больше или равно 64?) говорит нам о значении ведущего бита. Ответ на второй вопрос говорит нам о значении следующего бита и т. Д. Например, если число 77, то последовательность ответов true false, false, true, true, false, true сразу дает 1001101, двоичное представление 77.

Инвертирование функции.

В качестве примера полезности бинарного поиска в научных вычислениях мы вернемся к проблеме. С которой впервые столкнулись в упражнениях раздела 2.1: инвертирование возрастающей функции. Учитывая возрастающую функцию f и значение y, а также открытый интервал [lo, hi), наша задача состоит в том. Чтобы найти такое значение x в интервале. Что f(x) = y. В этой ситуации мы используем действительные числа в качестве конечных точек нашего интервала. А не целые числа. Но мы используем тот же самый существенный подход. Который мы использовали для угадывания скрытого целого числа в задаче

x в интервале, пока интервал не будет достаточно мал, чтобы мы знали значение x с желаемой точностью). Которое мы берем в качестве аргумента функции. Этот рисунок иллюстрирует первый шаг.

Двоичный поиск для инвертирования возрастающей функции

Программа bisection.py реализует эту стратегию. Мы начинаем с интервала (lo, hi), который, как известно, содержит x, и используем следующую рекурсивную процедуру:

  • Вычислить mid = (hi + lo) / 2.
  • Базовый случай: Если hilo меньше δ, то верните mid как оценку x.
  • Рекурсивный шаг: В противном случае проверьте, является ли

    f(midy. Если это так, ищите x в (lo, mid); если нет, ищите x в (mid, hi).

Ключом к такому подходу является идея о том , что функция увеличивается — для любых значений a и b, зная, что f(a)

Бинарный поиск в отсортированном массиве.

В течение большей части прошлого века люди использовали публикацию. Известную как словарь чтобы найти определение слова. Записи появляются по порядку, отсортированному по определяющему их ключу (слову). Подумайте о том, как вы будете искать слово в словаре. Решение, основанное на грубой силе, состояло бы в том. Чтобы начать с самого начала. Исследовать каждую запись по очереди и продолжать. Пока не найдете нужное слово.

Никто не использует этот подход: вместо этого вы открываете словарь на какой-то внутренней странице и ищете слово на этой странице. Если он есть. Вы закончили; в противном случае вы исключаете из рассмотрения и повторения либо часть словаря до текущей страницы. Либо часть словаря после текущей страницы.

Фильтр исключений.

Теперь мы используем двоичный поиск для решения проблемы существования: есть ли данный ключ в отсортированной базе данных ключей? Например, при проверке правописания слова вам нужно только знать, есть ли ваше слово в словаре. И не интересоваться его определением.

При компьютерном поиске мы храним информацию в массиве, отсортированном по ключу. Двоичный поисковый код в binarysearch.py отличается от других наших приложений двумя деталями. Во-первых, длина массива n не обязательно быть силой двух. Во-вторых, он должен допускать возможность того, что искомый элемент не находится в массиве. Клиентская программа реализует фильтр исключений: она считывает отсортированный список строк из файла. Который мы называем белым списком (например, white.txt) и произвольной последовательности строк из стандартного ввода (например,

emails.txt) и записывает в последовательность те, которых нет в белом списке.


Сортировка вставки

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

Алгоритм грубой силы, который мы рассматриваем, известен как сортировка вставки. Он основан на простом подходе. Который люди часто используют для организации рук игральных карт — то есть рассматривают карты по одной и вставляют каждую на свое место среди уже рассмотренных (сохраняя их отсортированными).

Программа insertion.py содержит реализацию sort()функции. Которая имитирует этот процесс для сортировки элементов в массиве a[]длины n. Тестовый клиент читает все строки из стандартного ввода, помещает их в массив. Вызывает sort()функцию для их сортировки. А затем записывает отсортированный результат в стандартный вывод. Попробуйте запустить его. Чтобы отсортировать маленькие tiny.txt файл. Также попробуйте запустить его для сортировки намного большего

размера tomsawyer.txt файл, но будьте готовы ждать долго!

Внешний цикл сортирует первые iзаписи в массиве; внутренний цикл может завершить сортировку. Поместив a[i]ее в нужное положение в массиве.

Трассировка сортировки вставки

Математический анализ.

sort()Функция содержит whileцикл, вложенный в forцикл, который предполагает. Что время выполнения квадратично. Однако мы не можем сразу сделать этот вывод, потому whileчто цикл завершается. Как только a[j]он больше или равен a[j-1].

  • В лучшем случае. Когда входной массив уже находится в отсортированном порядке. Внутренний цикл составляет не более чем сравнение (чтобы узнать, что

    a[j-1]меньше или равноa[j]), поэтому общее время выполнения линейно.

  • В худшем случае. При обратной сортировке входов внутренний цикл не завершается до тех пор. Пока j не станет равным 0. Таким образом. Частота выполнения инструкций во внутреннем цикле составляет 1 + 2 + … + n-1 ~ n2/2.
  • Средний случай. Когда вход произвольно упорядочен, мы ожидаем. Что каждый новый вставляемый элемент с одинаковой вероятностью попадет в любую позицию. Так что элемент будет двигаться в среднем наполовину влево. Таким образом, мы ожидаем. Что время выполнения будет 1/2 + 2/2 + … + (n-1)/2 ~ n2/2.

Эмпирический анализ.

Программа timesort.py реализует тест удвоения для функций сортировки.

Мы можем использовать его для подтверждения нашей гипотезы о том. Что сортировка вставки квадратична для случайно упорядоченных файлов:

% python >>>>>> импорт вставки >>>>>> импорт timesort >>>>>> timesort.doublingTest(insertion.sort, 128, 100) 128 3.67 256 3.73 512 4.21 1024 4.19 2048 4.11 

Чувствительность к входным сигналам.

Обратите внимание. Что doublingTest()функция в timesort.py принимает параметр mи выполняет mэксперименты для каждого размера массива. А не только для одного. Одна из причин этого заключается в том. Что время выполнения сортировки вставки чувствительно к ее входным значениям. Неверно категорически предсказывать, что время выполнения сортировки вставки будет квадратичным. Потому что ваше приложение может включать входные данные. Для которых время выполнения линейно.

Сопоставимые ключи.

Мы хотим иметь возможность сортировать любой тип данных, который имеет естественный порядок. К счастью, наши функции сортировки вставки и двоичного поиска работают не только со строками. Но и с любым сопоставимым типом данных. Вы можете сделать пользовательский тип сопоставимым, реализовав шесть специальных методов. Соответствующих операторам==,!=,,>, и.>= На самом деле. Наши функции сортировки вставки и двоичного поиска полагаются только на оператора. Но лучше реализовать все шесть специальных методов.


Mergesort

Обзор сортировки слияний

Чтобы разработать более быстрый алгоритм сортировки. Мы используем подход Эта терминология относится к идее. Что один из способов решения проблемы состоит в том. Чтобы разделить ее на независимые части, завоевать их независимо. А затем использовать решения для частей. Чтобы разработать решение для полной проблемы. Чтобы отсортировать массив с помощью этой стратегии, мы делим его на две половины. Сортируем две половины независимо друг от друга. А затем объединяем результаты для сортировки полного массива. Этот метод известен как mergesort.Для сортировки[lo, hi) мы используем следующую рекурсивную стратегию:

  • Базовый случай: Если размер подмножества равен 0 или 1, он уже отсортирован.
  • Рекурсивный шаг: В противном случае вычислите mid = (hi + lo)/2, отсортируйте (рекурсивно) два подмассива a[lo, mid) и a[mid, hi) и объедините их.

Программа merge.py это реализация. Как и с insert.py, тестовый клиент считывает все строки из стандартного ввода, помещает их в массив. Вызывает sort()функцию для их сортировки. А затем записывает отсортированный результат в стандартный вывод. Попробуйте запустить его. Чтобы отсортировать мелкие tiny.txt файл и то гораздо больше tomsawyer.txt файл.

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

След слияния в mergesort

Математический анализ.

Анализ слияний Внутренний цикл mergesort сосредоточен на вспомогательном массиве. forЦикл включает в себя n итераций. Поэтому частота выполнения инструкций во внутреннем цикле пропорциональна сумме длин подмассивов по всем вызовам рекурсивной функции. Значение этого количества появляется. Когда мы упорядочиваем вызовы по уровням в соответствии с их размером. Для простоты предположим, что n-степень 2 при n=2k . На первом уровне у нас есть один вызов размера n; на втором уровне у нас есть два вызова размера n/2; на третьем уровне у нас есть четыре вызова размера n/4; и так далее. Вплоть до последнего уровня с n/2 вызовами размера 2. Существует ровно k = lg n уровней. Дающих общую сумму n lg n для частоты выполнения инструкций во внутреннем цикле mergesort. Это уравнение оправдывает гипотезу о том. Что время работы mergesort линеарифмично.

Когда n не является степенью 2, подмассивы на каждом уровне не обязательно имеют одинаковый размер. Но число уровней все равно логарифмическое. Поэтому линеарифмическая гипотеза оправдана для всех n.

Эмпирический анализ.

Мы можем запустить программу timesort.py выполнить тест удвоения для подтверждения нашей гипотезы о том. Что mergesort имеет время выполнения n lg n для случайно упорядоченных файлов:

% python >>>>>> импорт слияние >>>>>> импорт timesort >>>>>> timesort.doublingTest(merge.sort, 128, 100) 128 1.84 256 2.15 512 2.22 1024 2.17 2048 2.13 4096 2.12 8192 2.14 

Квадратично-линеаризованная пропасть.

Разница между n2 и n lg n имеет огромное значение в практическом применении. Понимание колоссальности этого различия-еще один важный шаг к пониманию важности разработки и анализа алгоритмов. Для очень многих важных вычислительных задач ускорение от квадратичного к линеарифмическому делает разницу между способностью решить проблему. Включающую огромное количество данных. И неспособностью эффективно решить ее вообще.


Сортировка системы Python

Python включает в себя две операции для сортировки. Метод sort()во встроенном listтипе данных переставляет элементы в базовом списке в порядке возрастания. Как merge.sort(). Напротив, встроенная функция sorted()оставляет базовый список в покое; вместо этого она возвращает новый список. Содержащий элементы в порядке возрастания. Этот интерактивный скрипт Python справа иллюстрирует оба метода.

% python >>>>>> a = [3, 1, 4, 1, 5] >>>>>> b = сортировка(a) >>> a [3, 1, 4, 1, 5] >>> b [1, 1, 3, 4, 5] >>>>>> a.сортировка() >>> a [1, 1, 3, 4, 5] >>> 

Системная сортировка Python использует версию mergesort. Скорее всего, он будет существенно быстрее (10-20×). Чем merge.py потому что он использует низкоуровневую реализацию. Которая не составлена на Python. Тем самым избегая существенных накладных расходов. Которые Python накладывает на себя. Как и в наших реализациях сортировки. Вы можете использовать системную сортировку с любым сопоставимым типом данных. Таким как встроенные strтипы данных Pythonint, и floatтипы данных.


Применение: Отсчеты частоты

Программа frequencycount.py считывает последовательность строк из стандартного ввода. А затем записывает таблицу различных найденных значений и количество раз. Когда каждое из них было найдено. В порядке убывания частот. Мы достигаем этого двумя видами.

Вычисление частот.

Наш первый шаг-сортировка строк на стандартном входе. В данном случае нас интересует не столько то. Что строки расположены в отсортированном порядке, сколько то. Что сортировка объединяет равные строки. Если входной сигнал

быть или не быть 

тогда результат сортировки таков

be be not или to to to 

с равными строками, подобными трем вхождениямto, сведенным вместе в массив. Теперь, имея в массиве одинаковые строки, мы можем сделать один проход через массив. Чтобы вычислить все частоты. CounterКласс, как определено в counter.py из раздела 3.3 следует. Что это идеальный инструмент для этой работы.

Сортировка частот.

Далее мы сортируем Counterобъекты по частоте. Мы можем сделать это в клиентском коде, увеличив Counterтип данных. Чтобы включить шесть методов сравнения для сравнения Counterобъектов по их количеству. Таким образом, мы просто сортируем массив Counterобъектов. Чтобы переставить их в порядке возрастания частоты! Затем мы переворачиваем массив так, чтобы элементы располагались в порядке убывания частоты. Наконец, мы записываем каждый Counterобъект в стандартный вывод.

Закон Зипфа.

Приложение. Выделенное в frequencycount.py элементарный лингвистический анализ: какие слова чаще всего встречаются в тексте? Явление, известное как закон Ципфа, гласит. Что частота i-го наиболее часто встречающегося слова в тексте из m различных слов пропорциональна 1/i. Попробуй убежать frequencycount.py на большой leipzig100k.txt, leipzig200k.txt, и leipzig1m.txt файлы. Чтобы наблюдать это явление.


Вопросы и ответы

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

Ответ-Чтобы избавить себя от значительной боли. Примечательным примером является бинарный поиск. Например, теперь вы понимаете бинарный поиск; классическим упражнением в программировании является создание версии. Которая использует whileцикл вместо рекурсии. Попробуйте решить первые три упражнения из этого раздела, не оглядываясь на код из книги. В знаменитом эксперименте Джон Бентли однажды попросил нескольких профессиональных программистов сделать это. И большинство их решений оказались неверными.

Вопрос: Зачем вводить алгоритм mergesort, если Python предоставляет эффективный sort()метод. Определенный в listтипе данных?

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

Вопрос: Каково время выполнения следующей версии сортировки вставки в массиве, который уже отсортирован?

def sort(a): n = len(a) for i in range(1, n): for j in range(i, 0, -1): if a[j] ) остальное: перерыв 

A. Квадратичное время в Python 2; линейное время в Python 3. Причина в том. Что в Python 2 range()есть функция. Которая возвращает массив целых чисел длины. Равной длине диапазона (что может быть бесполезно. Если цикл заканчивается рано изbreakreturn-за оператора or). В Python 3 range()возвращает итератор, который генерирует только столько целых чисел. Сколько необходимо.

Вопрос: Что произойдет, если я попытаюсь отсортировать массив элементов. Которые не все имеют один и тот же тип?

Ответ-Если элементы имеют совместимые типы (например, intиfloat), то все работает нормально. Например, смешанные числовые типы сравниваются в соответствии с их числовым значением. Поэтому 0 и 0.0 рассматриваются как равные. Если элементы имеют несовместимые типы (например, strи int), то Python 3 вызывает a TypeErrorво время выполнения. Python 2 поддерживает некоторые сравнения смешанных типов, используя имя класса для определения того. Какой объект меньше. Например, Python 2 рассматривает все целые числа как меньшие, чем все строки. Потому 'int'что лексикографически они меньше 'str'.

Вопрос: Какой порядок используется при сравнении строк с такими операторами, как ==и ?

Неофициально Python использует лексикографический порядок для сравнения двух строк. Как слова в книжном индексе или словаре. Например 'hello'и 'hello'равны, 'hello'и 'goodbye'неравны, и 'goodbye'меньше 'hello'. Более формально Python сначала сравнивает первый символ каждой строки. Если эти символы различаются, то строки в целом сравниваются так же. Как эти два символа сравниваются. В противном случае Python сравнивает второй символ каждой строки. Если эти символы различаются, то строки в целом сравниваются так же. Как эти два символа сравниваются. Продолжая таким образом, если Python достигает концов двух строк одновременно. То он считает их равными. В противном случае он считает более короткую строку меньшей. Python использует Unicode для сравнения символов. Мы перечислим несколько наиболее важных свойств:

  • '0' меньше '1', и так далее.
  • 'A' меньше 'B', и так далее.
  • 'a' меньше 'b', и так далее.
  • Десятичные цифры ('0' to '9') меньше, чем прописные буквы ('A' to 'Z').
  • Прописные буквы ('A' to 'Z') меньше, чем строчные буквы ('a' to 'z').


Упражнения

  1. Разработать реализацию questions.py это принимает максимальное число nв качестве аргумента командной строки (оно не обязательно должно быть степенью 2). Докажите, что ваша реализация верна.

  2. Составьте нерекурсивную версию binarysearch.py.

  3. Изменить binarysearch.py таким образом, если ключ поиска находится в массиве . Он возвращает наименьший индексi, для которого a[i]равенkey, а в противном случае он возвращает наибольший индексi, для которого a[i]меньше key(или -1если такого индекса не существует).

  4. Опишите, что произойдет, если вы примените двоичный поиск к неупорядоченному массиву. Почему бы вам не проверить, отсортирован ли массив перед каждым вызовом двоичного поиска? Не могли бы вы проверить, что элементы, которые исследует бинарный поиск. Находятся в порядке возрастания?

  5. Опишите, почему желательно использовать неизменяемые ключи с двоичным поиском.

  6. Пусть f() - монотонно возрастающая функция с f(a) f(b) > 0. Составьте программу. Которая вычисляет значение > x такое. Что f(x) = 0 (с точностью до заданного допуска ошибок).

  7. Добавить код в insertion.py для получения приведенного выше следа.

  8. Добавить код в merge.py для получения приведенного выше следа.

  9. Дайте трассировки сортировки вставки и mergesort в стиле трасс, показанных выше. Для входных it was the best of times it wasданных .

  10. Составьте программуdedup.py, которая считывает строки из стандартного ввода и записывает их в стандартный вывод с удалением всех дубликатов (и в отсортированном порядке).

  11. Составьте версию mergesort, как определено в merge.py, который создает вспомогательный массив в каждом рекурсивном вызове to _merge()вместо того. Чтобы создавать только один вспомогательный массив in sort()и передавать его в качестве аргумента. Какое влияние это изменение оказывает на производительность?

  12. Составьте нерекурсивную версию mergesort, как определено в merge.py...

  13. Найдите частотное распределение слов в вашей любимой книге. Подчиняется ли он закону Ципфа?


Творческие Упражнения

Следующие упражнения предназначены для того. Чтобы дать вам опыт в разработке быстрых решений типичных проблем. Подумайте об использовании бинарного поиска. Mergesort или разработке собственного алгоритма Реализуйте и протестируйте свой алгоритм.

  1. Медиана. Изучите функцию median()stdstats.pyВ. Он вычисляет медиану заданного массива чисел в линеарифмическом времени. Обратите внимание. Что это работает, сводя проблему к сортировке.

  2. Режим. Добавьте к stdstats.pyфункцииmode(), которая вычисляет в линеарифмическом времени режим (значение. Которое встречается чаще всего) последовательности из n целых чисел. Подсказка: Сведите к сортировке.

  3. Целочисленная сортировка. Составьте линейно-временной фильтр. Считывающий со стандартного входа последовательность целых чисел в диапазоне от 0 до 99 и записывающий целые числа в отсортированном порядке на стандартном выходе. Например, представлена входная последовательность

    98 2 3 1 0 0 0 3 98 98 2 2 2 0 0 0 2 

    ваша программа должна записать выходную последовательность

    0 0 0 0 0 0 1 2 2 2 2 2 3 3 98 98 98 
  4. Пол и потолок. Учитывая отсортированный массив из n сопоставимых ключей, составьте функцииfloor(), ceiling()которые возвращают индекс самого большого (или самого маленького) ключа. Не большего (или меньшего). Чем ключ аргумента в логарифмическом времени.

  5. Битонический максимум. Массив является битоническим, если он состоит из возрастающей последовательности ключей. За которой немедленно следует убывающая последовательность ключей. Учитывая битонический массив. Разработайте логарифмический алгоритм для нахождения индекса максимального ключа.

  6. Поиск в битоническом массиве. Учитывая битонический массив из n различных целых чисел. Разработайте алгоритм логарифмического времени. Чтобы определить. Находится ли данное целое число в массиве.

  7. Ближайшая пара. Учитывая массив из n поплавков, составьте функцию. Чтобы найти в линеарифмическом времени пару поплавков. Наиболее близких по значению.

  8. Самая дальняя пара. Учитывая массив из n поплавков, составьте функцию. Чтобы найти за линейное время пару целых чисел. Наиболее удаленных друг от друга по значению.

  9. Две суммы. Составьте функцию. Которая принимает в качестве аргумента массив из n целых чисел и определяет за линеарифмическое время. Суммируются ли любые два из них в 0.

  10. Три сум. Составьте функцию. Которая принимает в качестве аргумента массив из n целых чисел и определяет. Суммируются ли любые три из них в 0. Ваша программа должна выполняться за время. Пропорциональное n2 log n. Дополнительный кредит: Разработайте программу. Которая решает задачу за квадратичное время.

  11. Большинство. Учитывая массив из n элементов, элемент является большинством, если он появляется более n/2 раз. Составьте функцию. Которая принимает массив из n строк в качестве аргумента и идентифицирует большинство (если оно существует) в линейном времени.

  12. Общий элемент. Составьте функцию. Которая принимает в качестве аргумента три массива строк, определяет. Есть ли какая-либо строка. Общая для всех трех массивов, и если да. То возвращает одну такую строку. Время выполнения вашей функции должно быть линеарифмическим в общем количестве строк.

  13. Самый большой пустой интервал. Учитывая n временных меток для того момента, когда файл запрашивается с веб-сервера. Найдите наибольший интервал времени. В течение которого файл не запрашивается. Составьте программу для решения этой задачи за линейное время.

  14. Коды без префиксов. При сжатии данных набор строк не содержит префиксов, если ни одна строка не является префиксом другой. Например, набор строк 01, 10, 0010, и 1111не содержит префиксов, но набор строк 01, 10, 0010, 1010не является префиксом. Потому 10что является префиксом of 1010. Составьте программу. Которая считывает набор строк из стандартного ввода и определяет. Не содержит ли этот набор префиксов.

  15. Разделение. Составьте функцию. Которая сортирует массив, который, как известно. Имеет не более двух различных значений. Совет: Поддерживайте два указателя, один из которых начинается с левого конца и движется вправо. Другой начинается с правого конца и движется влево. Сохраняйте инвариант, что все элементы слева от левого указателя равны меньшему из двух значений. А все элементы справа от правого указателя равны большему из двух значений.

  16. Голландский национальный флаг. Составьте функцию. Которая сортирует массив, который, как известно. Имеет не более трех различных значений. (Edsgar Дейкстра назвал это голландский национальный флаг проблема. Потому что в результате получается три Подсказка: свести к предыдущей задаче. Путем разделения массива на две части со всеми элементами. Имеющими наименьшее значение в первой части. А все остальные элементы во второй части. То раздел второй части.

  17. Ртуть. Составьте рекурсивную программу. Которая сортирует массив случайно упорядоченных отдельных элементов. Совет: Используйте метод, подобный описанному в предыдущем упражнении. Сначала разбейте массив на левую часть со всеми элементами меньше v, затем v, а затем правую часть со всеми элементами больше v. Затем рекурсивно отсортируйте две части. Дополнительный кредит: Измените свой метод (при необходимости), чтобы он работал правильно. Когда элементы не обязательно различны.

  18. Обратный домен. Составьте программу для чтения списка доменных имен из стандартного ввода и записи обратных доменных имен в отсортированном порядке. Например, обратная область cs.princeton.eduис edu.princeton.cs. Это вычисление полезно для анализа веб - журналов. Для этого создайте тип данныхDomain, реализующий специальные методы сравнения. Используя обратный порядок доменных имен.

  19. Локальный минимум в массиве. Учитывая массив из n поплавков, составьте функцию. Чтобы найти в логарифмическом времени локальный минимум (индекс iтакой. Что a[i] и a[i] ).

  20. Дискретное распределение. Разработайте быстрый алгоритм для многократной генерации чисел из дискретного распределения. Учитывая массив p[]неотрицательных поплавков, сумма которых равна 1, цель состоит в том. Чтобы вернуть индекс iс вероятностью p[i]. Сформируйте массив s[]кумулированных сумм таким образом. Чтобы это s[i]была сумма первых iэлементов p[]. Теперь сгенерируйте случайный поплавок rмежду 0 и 1 и используйте двоичный поиск. Чтобы вернуть индексi, для которого s[i] ≤ r он нужен .

  21. Рифмующиеся слова. Составьте список, который вы можете использовать для поиска рифмующихся слов. Используйте следующий подход:

    • Считайте в словаре слова в массив строк.
    • Переверните буквы в каждом слове (confound становится dnuofnoc, например).
    • Отсортируйте полученный массив.
    • Переверните буквы в каждом слове обратно в их первоначальный порядок.

    Например, confoundнаходится рядом с такими словами, как astoundи surroundв результирующем списке.