The art of programming
11.04
Sorting by Merging
Во время лекции 1946 года в школе Мура один из разработчиков ENIAC Джон Мокли (John Mauchly) заметил:
Требование, чтобы одна машина объединяла возможности вычислений и сортировки, может выглядеть как требование, чтобы один прибор использовался как ключ для консервов и как авторучка.
Ещё он отметил, что сортировка необходима для выполнения математических процедур и численных расчетов. А сама лекция была посвящена «сортировке слиянием».
Сортировка слиянием отрабатывает с одинаковой скоростью на любых массивах одинаковой длины, а временная сложность этого алгоритма — O(N log N). Идея сортировки слиянием в следующем:
1. Входной массив рекурсивно делится до подмассивов размером в один элемент, который считается отсортированным.
2. Элементы в подмассивах сравниваются попарно и заносятся по порядку. Они последовательно объединяются до получения одного отсортированного массива.
Сортировка слиянием стала одним из первых алгоритмов, разработанных в парадигме «разделяй и властвуй», когда задача разбивается на более мелкие, а ответ собирается из их решений. Сам алгоритм был написан для первого компьютера с хранимой в памяти программой — EDVAC. В первом проекте отчета об EDVAC, подготовленном Джоном фон Нейманом в 1945 году, уже упоминается задача сортировки. В то время такая задача представляла интерес как потенциальное нечисленное приложение ЭВМ. В 1948 году Нейман совместно с Германом Голдстайном (Herman Goldstine) опубликовал формальное описание алгоритма сортировки слиянием (Sorting based on meshing).
Можно заметить, что сортировка обладает недостатком — расходами на дополнительную память. Однако, методы сортировки тесно переплетались с развитием ЭВМ. До появления EDVAC существовали эффективные специализированные сортировальные машины. В отчёте 1945 года EDVAC описывался как проект в разработке, а реализация алгоритма сортировки была ярким примером подхода, при котором компьютер может быть «универсальной» вычислительной машиной. Такой подход в дальнейшем станет известен как «архитектура фон Неймана».
еще контент в этом сообществе
еще контент в этом соообществе
The art of programming
11.04
войдите, чтобы увидеть
и подписаться на интересных профи