Cтраница 2
Так, цепочку ЛАБОРАТОРИЯ нужно перевести в цепочку ААБИЛООРРТЯ. Приведенная ниже программа выполняет требуемое преобразование, используя метод обменной сортировки. [16]
Это улучшение приводит к самому лучшему на сегодняшний день методу сортировки массивов, который можно назвать обменной сортировкой с разделением. Он основан на сравнениях и обменах элементов, стоящих на возможно больших расстояниях друг от друга. [17]
Здесь желательно на какое-то время остановиться и подумать о том, как можно все это сделать. На первый взгляд кажется, что у этой проблемы есть простое решение, однако на самом деле все известные до сих пор решения достаточно сложные, особенно если их сравнить с программой 8.1. И в самом деле, довольно трудно разработать алгоритм обменного слияния, т.е. в рамках пространства памяти, занимаемого входными файлами, который обладал бы лучшими характеристиками и который мог бы стать альтернативой обменной сортировке. [18]
Алгоритм быстрой сравнительной сортировки был предложен Шеллом ( см. библиографию, гл. Алгоритм близок к оптимальному для сравнительных сортировок. Сортировка Шелла подобна обменной сортировке в том смысле, что она перемещает величины путем перестановки пар. Это приводит к тому, что величины, которые находятся не на месте, будут перемещаться быстрее, чем при простой обменной сортировке. [19]
Придумайте и реализуйте алгоритм сортировки, аналогичный быстрой сортировке, в котором расщепление осуществляется на основании самого старшего разряда имен: если этот разряд единица, то имя пересылается в правую часть таблицы, если этот разряд нуль, то имя пересылается в левую часть таблицы. Расщепления следующего уровня основываются на следующих разрядах имени. Этот метод известен как цифровая обменная сортировка. [20]
Существует целый ряд простых и сложных способов решения этрй задачи. На рис. 3.16 представлен фрагмент программы, выполняющей обменную сортировку, известную также как пузырьковая сортировка1), сортировка погружением или сортировка просеива-мием. Этот простой алгоритм сортировки основан на сравнении пары соседних величин в таблице и перестановке их в требуемом порядке. Такого вида сортирующий алгоритм не очень эффективен, но прост. Рассмотрим его на следующем примере. [21]
Число сравнений равно минимум ( п - 1), максимум ( п - 1) / 2; первое соответствует случаю наилучшего варианта числа обменов, второе - случаю наихудшего варианта. Среднее число сравнений отклоняется от промежуточного в большую сторону. При использовании метода обменной сортировки не только число сравнений оказывается несколько больше, но и число обменов оказывается не меньше, чем число перемещений при сортировке вставками. Если сравнивать метод обменной сортировки с сортировкой посредством выбора, то среднее число сравнений оказывается близким к половине, а среднее число обменов более чем вдвое больше числа операций вывода элементов при сортировке посредством выбора. [22]
Алгоритм быстрой сравнительной сортировки был предложен Шеллом ( см. библиографию, гл. Алгоритм близок к оптимальному для сравнительных сортировок. Сортировка Шелла подобна обменной сортировке в том смысле, что она перемещает величины путем перестановки пар. Это приводит к тому, что величины, которые находятся не на месте, будут перемещаться быстрее, чем при простой обменной сортировке. [23]
Число сравнений равно минимум ( п - 1), максимум ( п - 1) / 2; первое соответствует случаю наилучшего варианта числа обменов, второе - случаю наихудшего варианта. Среднее число сравнений отклоняется от промежуточного в большую сторону. При использовании метода обменной сортировки не только число сравнений оказывается несколько больше, но и число обменов оказывается не меньше, чем число перемещений при сортировке вставками. Если сравнивать метод обменной сортировки с сортировкой посредством выбора, то среднее число сравнений оказывается близким к половине, а среднее число обменов более чем вдвое больше числа операций вывода элементов при сортировке посредством выбора. [24]