Элементарные методы сортировки
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
дена к процедуре sort3 этой программы.
Три оператора присвоения, каждый из которых сопровождается оператором if, на деле реализуют операцию обмена. Мы вставляем ее непосредственно в программный код вместо использования вызова процедуры, поскольку они являются основой многих алгоритмов и часто попадают внутрь цикла.
Чтобы сконцентрироваться на алгоритмических вопросах, мы будем работать с алгоритмами, которые просто сортируют массивы целых в численном порядке. В общем, очень легко адаптировать такие алгоритмы для практического использования, включающего в себя работу с большими ключами или записями. В основном программы сортировки работают с записями двумя способами: либо они сравнивают и сортируют только ключи, либо передвигают записи целиком. Большинство алгоритмов, которые мы изучим можно применять, посредством их переформулировки в терминах этих двух операций, для произвольных записей. Если сортируемые записи довольно большие, то обычно пытаются избежать передвижения их посредством косвенной сортировки: при этом сами записи не переупорядочиваются, а вместо этого переупорядочивается массив указателей (индексов), так, что первый указатель указывает на самый маленький элемент и так далее. Ключи могут храниться либо с записями (если они большие), либо с указателями (если они маленькие). Если необходимо, то после сортировки записи можно упорядочить. Это описано дальше.
Программа sort3 использует даже более ограниченный доступ к файлу: это три операции вида сравнить две записи и обменять их, если нужно, чтобы поместить запись с меньшим ключом на первое место. Программы, ограниченные такими операциями интересны, поскольку они подходят для реализации на аппаратном уровне. Мы изучим их более подробно позднее.
Все примеры программ используют для сортировки глобальный массив. Это не означает, что такой подход лучше или хуже чем передача массива как параметра. Все зависит от точки зрения и конкретного алгоритма. Массив сделан глобальным только потому, что тогда примеры становятся короче и понятней.
Сортировка выбором
Один из самых простых методов сортировки работает следующим образом: находим наименьший элемент в массиве и обмениваем его с элементом находящимся на первом месте. Потом повторяем процесс со второй позиции в файле и найденный элемент обмениваем со вторым элементном и так далее пока весь массив не будет отсортирован. Этот метод называется сортировка выбором, поскольку он работает, циклически выбирая наименьший из оставшихся элементов, как показано на рисунке 1. При первом проходе символ пробела уходит на первое место, обмениваясь с буквой П. На втором проходе элемент В обменивается с элементом Р и так далее.
Следующая программа дает полную реализацию этого процесса. Для каждого i от 1 до N-1, она обменивает наименьший элемент из a [i..N] с a[i]:
По мере продвижения указателя i слева направо через файл, элементы слева от указателя находятся уже в своей конечной позиции (и их больше уже не будут трогать), поэтому массив становится полностью отсортированным к тому моменту, когда указатель достигает правого края.
Этот метод один из простейших, и он работает очень хорошо для небольших файлов. Его внутренний цикл состоит из сравнения a[i]<a[min] (плюс код необходимый для увеличения j и проверки на то, что он не превысил N), что вряд ли можно еще упростить.
Кроме того, хотя сортировка выбором является методом грубой силы, он имеет очень важное применение: поскольку каждый элемент передвигается не более чем раз, то он очень хорош для больших записей с маленькими ключами.
Сортировка вставкой
Метод сортировки вставкой, почти столь же прост, что и сортировка выбором, но гораздо более гибкий. Этот метод часто используют при сортировке карт: берем один элемент и вставляем его в нужное место среди тех, что мы уже обработали (тем самым оставляя их отортированными).
Рассматриваемый элемент вставляется в позицию посредством передвижения большего элемента на одну позицию вправо и затем размещением меньшего элемента в освободившуюся позицию, как показано на рисунке2. Так И при третьем шаге меньше всех остальных отсортированных элементов, поэтому мы топим его в начало массива. М больше И но меньше всех остальных, поэтому мы помещаем его между И и П, и так далее.
Этот процесс реализован в следующей программе. Для каждого i от 2 до N, подмассив a [1..i] сортируется посредством помещения a[i] в подходящую позицию среди уже отсортированных элементов:
Также как и при сортировке выбором, в процессе сортировки элементы слева от указателя i находятся уже в сортированном порядке, но они не обязательно находятся в своей последней позиции, поскольку их еще могут передвинуть направо чтобы вставить более маленькие элементы встреченные позже. Массив становится полностью сортированным когда указатель достигает правого края.
Однако имеется еще одна важная деталь: программа insertion не всегда работает, поскольку while может проскочить за левый край массива, когда v самый меньший элемент массива. Чтобы исправить ситуацию, мы помещаем сторожевой ключ в a[0], делая его, по крайней мере, не больше, чем самый маленький ключ массива. Сторожевые элементы повсеместно используются в ситуациях подобных этой для предотвращения дополнительной проверки (в данном случае j>0), что почти всегда помогает во внутренних ци?/p>