Алгоритмы сортировки: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
Нет описания правки |
||
Строка 33:
Итак, мы придумали алгоритм для сортировки любого набора чисел. на каждом шаге наш алгоритм находит наименьшее число в исходном наборе, удаляет его оттуда и записывает в конец набора, представляющего результат сортировки. Такую сортировку называют ''сортировкой поиском минимума''.
Перейдем теперь от алгоритма к его реализации.
==Реализация алгоритма== Пусть нам дан массив из ''N'' чисел. Заметим, что количество чисел, которые мы храним, по ходу работы алгоритма не изменяется: на каждом шаге мы просто переносим одно из чисел из исходного набора в результирующий. Поэтоум нам нет надобности заводить новый массив для хранения результата: мы сможем хранить его в освободившихся ячейках старого массива. После ''k''-го хода результат содержит ''k'' чисел, а исходный набор - ''N''-''k''. Договоримся, что текущий результат мы будем хранить в первых k элементах массива. Разберем подробнее, как это можно реализовать. Для этого вновь обратимся к нашему примеру:
Строка 70 ⟶ 73 :
end
Алгоритм сортировки поиском минимума реализован.
==Анализ работы алгоритма==
Предположим, что кто-то придумал еще один алгоритм сортировки. Как сравнить его с нашим. Чем он может быть лучше ли хуже? Ясно, что результаты работы обоих алгоритмов обязаны совпадать, в противном случае можно сказать, что один из них (надеемся, что не наш!) работает неправильно.
Таким образом, алгоритмы надо сравнивать по другим параметрам. Такими параметрами в первую очередь являются ''время'' работы алгоритма и требуемая для его работы ''память''. Поскольку сравнивать наш алгоритм нам пока не с чем, попробуем просто оценить его по указанным параметрам.
Поскольку время работы алгоритма зависит от того, на каком языке программирования был написан код, как он был скомпилирован, на каком компьютере выполняется и т. д., то мы будем считать не время работы алгоритма, а ''количество операций'', выполняемых алгоритмом. Наш алгоритм ''N''-1 раз выполняет поиск минимума - в первый раз минимум ищется среди ''N'' элементов, и на это тербуется порядка N операций, второй раз - среди ''N''-1 элемента, и т. д. Таким образом, на посик минимума всего потребуется N + (N-1) + ... + 3 + 2 = (N+2)(N-1)/2 опреаций, что примерно равно N<sup>2</sup>/2 операций. На перестановку минимумов на свои места требуется порядка N операций. При больших N N<sup>2</sup>/2 много больше N, поэтому операциями перестановки максимума можно пренебречь, и сказать, что наш алгоритм работает за время порядка N<sup>2</sup>/2, где N - количество чисел. Алгоритмы, которые требуют порядка CN<sup>2</sup>/2 операций (где С - некоторая константа, не зависящая от N), называют ''квадратичными''. Посмотрим, как растет величина N<sup>2</sup> с ростом N:
N 10 1000 10000 1000000
N<sup>2</sup>/2 100 1000000 100000000 1000000000000
| |||