Алгоритмы сортировки: различия между версиями

Поскольку время работы алгоритма зависит от того, на каком языке программирования был написан код, как он был скомпилирован, на каком компьютере выполняется и т. д., то мы будем считать не время работы алгоритма, а ''количество операций'', выполняемых алгоритмом. Наш алгоритм ''N''-1 раз выполняет поиск минимума - в первый раз минимум ищется среди ''N'' элементов, и на это тербуется порядка N операций, второй раз - среди ''N''-1 элемента, и т. д. Таким образом, на посик минимума всего потребуется N + (N-1) + ... + 3 + 2 = (N+2)(N-1)/2 опреаций, что примерно равно N²/2 операций. На перестановку минимумов на свои места требуется порядка N операций. При больших N N²/2 много больше N, поэтому операциями перестановки максимума можно пренебречь, и сказать, что наш алгоритм работает за время порядка N²/2, где N - количество чисел. Алгоритмы, которые требуют порядка CN²/2 операций (где С - некоторая константа, не зависящая от N), называют ''квадратичными''. Посмотрим, как растет величина N² с ростом N: