Алгоритм сортировки
В информатике алгоритм сортировки — это алгоритм , который упорядочивает элементы списка . Наиболее часто используемые порядки — числовой порядок и лексикографический порядок , а также восходящий или нисходящий. Эффективная сортировка важна для оптимизации эффективности других алгоритмов (например, алгоритмов поиска и слияния ), которые требуют, чтобы входные данные находились в отсортированных списках. Сортировка также часто полезна для канонизации данных и для создания удобочитаемого вывода.
Для оптимальной эффективности входные данные должны храниться в структуре данных , допускающей произвольный доступ , а не только в последовательном доступе .
С самого начала вычислительной техники проблема сортировки привлекала большое внимание исследователей, возможно, из-за сложности ее эффективного решения, несмотря на ее простую и знакомую формулировку. Среди авторов ранних алгоритмов сортировки около 1951 года была Бетти Холбертон , работавшая над ENIAC и UNIVAC . [1] [2] Пузырьковая сортировка была проанализирована еще в 1956 году. [3] Асимптотически оптимальные алгоритмы известны с середины 20-го века – новые алгоритмы изобретаются до сих пор, широко используемый Timsort датируется 2002 годом, а библиотека sort впервые опубликован в 2006 году.
Алгоритмы сравнительной сортировки имеют фундаментальное требование Ω( n log n ) сравнений (некоторые входные последовательности потребуют кратного n log n сравнений, где n — количество элементов в массиве для сортировки). Алгоритмы, не основанные на сравнениях, такие как сортировка с подсчетом , могут иметь лучшую производительность.
Алгоритмы сортировки преобладают на начальных занятиях по информатике , где обилие алгоритмов для решения задачи обеспечивает мягкое введение в различные основные концепции алгоритмов, такие как нотация большого O , алгоритмы « разделяй и властвуй », структуры данных , такие как кучи и двоичные файлы . деревья , рандомизированные алгоритмы , анализ наилучшего, наихудшего и среднего случаев , компромиссы между временем и пространством , а также верхние и нижние границы .
Оптимальная (с наименьшим количеством сравнений и перестановок) или быстрая сортировка небольших массивов (т. е. с учетом особенностей машины) по-прежнему остается открытой исследовательской проблемой, и решения известны только для очень маленьких массивов (менее 20 элементов). Точно так же оптимальная (по различным определениям) сортировка на параллельной машине является открытой темой исследования.
