Алгоритм

Сравнение алгоритмов

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

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

Сортировка

Это пример алгоритма для сортировки карточек с изображенными на них цветами в кучи одного цвета:

1. Соберите все карты.
2. Возьмите карту из руки и посмотрите на цвет карты.
3. Если уже есть стопка карт этого цвета, положите эту карту в эту стопку.
4. Если в стопке нет карт этого цвета, сделайте новую стопку карт только этого цвета.
5. Если в руке все еще есть карта, вернитесь ко второму шагу.
6. Если в вашей руке не осталось ни одной карты, то карты сортируются. Вы закончили.

Сортировка по номерам

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

Игроки начинают со стопки карт, которые не были отсортированы.

Первый алгоритм

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

1. Если стопка карт пуста или содержит только одну карту, она отсортирована; вы закончили.
2. Возьмите стопку карт. Посмотрите на первую карту (верхнюю) из стопки.
3. Карта, на которую вы смотрите, это карта А. Позиция, на которой находится карта А в данный момент, находится в стопке P.
4. Если после карты А в стопке больше нет карт, перейдите к шагу 8.
5. Следующая карта в стопке - карта B.
6. Если карта B имеет меньшее число, чем карта A, поменяйте местами карты A и B. Запомните, что вы это сделали. Когда вы меняете карты местами, не меняйте позицию P.
7. Если в стопке после позиции P есть еще одна карта, посмотрите на нее; вернитесь к шагу 3.
8. Если во время последнего хода вы не поменяли местами ни одну из карт, вы закончили; стопка карт отсортирована.
9. В противном случае вернитесь к шагу 2.

Пошаговый пример

Возьмем стопку карточек с числами "5 1 4 2 8" и отсортируем ее от наименьшего числа к наибольшему, используя данный алгоритм. На каждом шаге алгоритм сравнивает элементы, выделенные жирным шрифтом. Верхняя часть стопки карточек находится слева.

Первый проход:
( 5 1 4 2 8 ) → {\displaystyle \to } ( 1 5 4 2 8 ) Здесь алгоритм сравнивает первые два элемента и меняет их местами.
( 1 5 4 2 8 ) → {\displaystyle \to } ( 1 4 5 2 8 )
( 1 4 5 2 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 ) Эти элементы уже расположены по порядку, поэтому алгоритм не меняет их местами.
Второй проход:
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Теперь стопка карт уже отсортирована, но наш алгоритм этого не знает. Алгоритму нужен один проход без подмены, чтобы узнать, что она отсортирована.
Третий проход:
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Наконец, массив отсортирован, и алгоритм может быть остановлен.

История

Это простой для понимания алгоритм сортировки. Компьютерные ученые назвали его Bubble sort, потому что меньшие элементы будут подниматься к вершине, меняя свое положение при каждом проходе. К сожалению, алгоритм не очень хорош, потому что для сортировки требуется много времени (много проходов через стопку карточек).

Второй алгоритм

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

Основная идея

1. Если в стопке нет карт или есть только одна карта, она отсортирована, и вы закончили.
2. Разделите стопку карт на две половины примерно одинакового размера. Если карт нечетное количество, то в одной из двух стопок будет на одну карту больше, чем в другой.
3. Отсортируйте каждую из двух стопок, используя этот алгоритм (Для каждой стопки начните с пункта 1 этого списка).
4. Объедините две отсортированные стопки вместе, как описано ниже.
5. В результате вы получите отсортированную стопку карт. Вы закончили.

Объединение двух стеков вместе

Это работает с двумя стопками карт. Одна из них называется A, другая - B. Есть третья стопка, пустая в начале, называется C. В конце она будет содержать результат.

1. Если стопка A или стопка B пуста, положите все карты из непустой стопки на стопку C; вы закончили, стопка C - результат слияния. (Примечание: возьмите всю стопку и положите ее на стопку C; если делать это по карточкам, порядок изменится и не будет работать так, как нужно).
2. Посмотрите на верхние карты стопки А и стопки В. Положите карту с меньшим номером на верх стопки С. Если в стопке С не было карт, то теперь в ней будет одна карта.
3. Если в стопке А или стопке В остались карты, вернитесь к шагу 1 для их сортировки.

История

Джон фон Нейман разработал этот алгоритм в 1945 году. Он не назвал его "Сортировка по числам", а назвал его Mergesort. Это очень хороший алгоритм сортировки по сравнению с другими.

Третий алгоритм

Первый алгоритм занимает гораздо больше времени для сортировки карт, чем второй, но его можно улучшить (сделать лучше). Если посмотреть на пузырьковую сортировку, то можно заметить, что карты с большими номерами перемещаются с вершины стопки довольно быстро, а карты с малыми номерами в нижней части стопки требуют много времени для подъема (перемещения на вершину). Идея улучшения первого алгоритма заключается в следующем:

Вместо того чтобы сравнивать две карты, находящиеся рядом друг с другом, в начале выбирается "особая" карта. Затем все остальные карты сравниваются с этой картой.

1. Мы начинаем со стека A. Есть еще два стека B и C, которые будут созданы позже.
2. Если в стопке A нет карт или есть только одна карта, то сортировка закончена.
3. Из стопки A выбирается карта, по возможности наугад. Это называется поворотом.
4. Все оставшиеся карты из стопки А сравниваются с этим стержнем. Карты с меньшим числом переходят в стопку B, карты с равным или большим числом - в стопку C.
5. Если в стопках B или C есть какие-либо карты, эти стопки нужно отсортировать с помощью того же алгоритма (начните с позиции 1 этого списка поочередно для стопки B и стопки C).
6. Выполнено. В отсортированной стопке карт сначала находится отсортированная стопка B, затем стержень, а затем отсортированная стопка C.

История

Этот алгоритм был разработан К. А. Р. Хоаром в 1960 году. Сегодня это один из наиболее широко используемых алгоритмов сортировки. Он называется Quicksort.

Анимация, показывающая, как работает пузырьковая сортировка


Сортировка 7 чисел с помощью второго алгоритма сортировки по числам (Mergesort)


Третий алгоритм сортировки карточек. В качестве стержня выбирается элемент с красной полосой. В начале это элемент, расположенный справа. Этот алгоритм называется Quicksort.

Составление алгоритмов вместе

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

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

Похожие страницы

• Евклидов алгоритм был найден более 2000 лет назад. Он позволяет найти наибольший общий делитель двух чисел.