2 ГЛАВА 'Сортировка выбором'
А теперь объединим все, что вы узнали, во втором алгоритме: сортировке выбором. Чтобы освоить этот алгоритм, вы должны понимать, как работают массивы и списки и «О-большое». Допустим, у вас на компьютере записана музыка и для каждого исполнителя хранится счетчик воспроизведений.
Вы хотите отсортировать список по убыванию счетчика воспроизведений, чтобы самые любимые исполнители стояли на первых местах . Как это сделать?
Одно из возможных решений - пройти по списку и найти исполнителя с наибольшим количеством воспроизведений . Этот исполнитель добавляется в новый список.
Потом то же самое происходит со следующим по количеству воспроизведений исполнителем .
Продолжая действовать так, мы получаем отсортированный список.
А теперь попробуем оценить происходящее с точки зрения теории вычислений и посмотрим, сколько времени будут занимать операции. Напомним, что время О(n) означает, что вы по одному разу обращаетесь к каждому элементу списка. Например, прИ: простом поиске по списку исполнителей каждый исполнитель будет проверен один раз.
Чтобы найти исполнителя с наибольшим значением счетчика воспроизведения, необходимо проверить каждый элемент в списке. Как вы уже видели, это делается за время О(n). Итак, имеется операция, выполняемая за время О(n), и ее необходимо выполнить n раз :
Все это требует времени О(n х n), или O(n^2 ).
Алгоритмы сортировки очень полезны. Например, теперь вы можете отсортировать:
* имена в телефонной книге;
* даты путешествий;
* сообщения электронной почты (от новых к старым).
Алгоритм сортировки выбором легко объясняется, но медленно работает. Быстрая сортировка - эффективный алгоритм сортировки, который выполняется за время О(n log n). Но мы займемся этой темой в следующей главе!