Для простоты будем предполагать, что размер массива есть степень двойки. (Как мы увидим в главе 4, это ограничение не очень существенно.) Тогда на каждом шаге сортируемый участок делится на две равные половины. Разбиение на части (вычисление границы) требует времени 0(1), а слияние—времени (-)(•//.). Получаем соотношение
Как мы увидим в главе 4, это соотношение влечёт Т(п) = O(nlogn), где через log мы обозначаем двоичный логарифм (основание логарифмов, впрочем, не играет роли, так как приводит лишь к изменению константы). Поэтому для больших та сортировка слиянием эффективнее сортировки вставками, требующей времени O(n2).
О пользе быстрых алгоритмов
Как мог бы сказать Козьма Прутков, хороший алгоритм подобен острому ножу – тот и другой достигают цели легко и просто. Другое сравнение: человек, пользующийся плохим алгоритмом, подобен повару, отбивающему мясо отвёрткой: едва съедобный и малопривлекательный результат достигается ценой больших усилий.
Часто разница между плохим и хорошим алгоритмом более существенна, чем между быстрым и медленным компьютером. Пусть мы хотим отсортировать массив из миллиона чисел. Что быстрее – сортировать его вставками на суперкомпьютере (100 миллионов операций в секунду) или слиянием на домашнем компьютере (1 миллион операций)? Пусть к тому же сортировка вставками написана на ассемблере чрезвычайно экономно, и для сортировки п чисел нужно, скажем, лишь 2n2 операций. В то же время алгоритм слиянием написан без особой заботы об эффективности и требует 50nlogn операций. Для сортировки
для суперкомпьютера и всего
для домашнего компьютера.
Мы видим, что разработка эффективных алгоритмов не менее важна, чем разработка быстрой электроники. В этой области также происходит заметный прогресс.
Обменная сортировка
Упорядочение элементов в списке является важным для многих приложений. Например, некоторый список может сортировать записи по их инвентарным номерам для обеспечения быстрого доступа к элементу, словарь сохраняет слова в алфавитном порядке и регистрационные порядковые записи студентов — по их номерам социального страхования.
Для создания упорядоченного списка мы вводим алгоритм сортировки, называемый ExchangeSort, который упорядочивает элементы в возрастающем порядке. Этот алгоритм иллюстрируется списком 8, 3, 6, 2 и создает упорядоченный список 2, 3, 6, 8.
Индекс 0: Рассмотрим полный список 8, 3, 6, 2. Элемент с индексом 0 сравнивается с каждым последующим элементом в списке с индексами 1, 2 и 3. Для каждого сравнения, если последующий элемент меньше, чем элемент с индексом 0, эти два элемента меняются местами. После выполнения всех сравнений наименьший элемент помещается в позицию с индексом 0.
Индекс 1: При уже помещенном в позицию с индексом 0 самом маленьком элементе рассмотрим подсписок 8, 6, 3. Принимаются во внимание только элементы от индекса 1 до конца списка. Элемент с индексом 1 сравнивается с последующими элементами с индексами 2 и 3. Для каждого сравнения, если больший элемент находится в позиции с индексом 1, то два элемента меняются местами. После выполнения сравнений второй наименьший элемент в списке сохраняется в позиции с индексом 1.
Индекс 2: Рассмотрим подсписок 8, 6. Этот процесс продолжается для подсписка из двух элементов с индексами 2 и 3. Между элементами выполняется простое сравнение, в результате которого происходит обмен.
У нас остался только один элемент с индексом 3, и список отсортирован*
В C++ функция ExchangeSort использует вложенные циклы. Предположим, что размер списка задается значением п. Внешний цикл приращивает индекс 1 в диапазоне от 0 до п-2. Для каждого индекса i сравним последующие элементы при j=i+l, 1+2,..., п-1. Выполним сравнение и поменяем местами элементы, если list[i] > list[j].
У нас остался только один элемент с индексом 3, и список отсортирован
В C++ функция ExchangeSort использует вложенные циклы. Предположим, что размер списка задается значением n. Внешний цикл приращивает индекс 1 в диапазоне от 0 до n-2. Для каждого индекса i сравним последующие элементы при j=i+l, 1+2,..., n-1. Выполним сравнение и поменяем местами элементы, если list[i] > list[j].