Метод сортировки пузырьками и сортировка методом отыскания наименьшего (наибольшего) ключа

Рассмотрим методы указанные в заглавии на уровне идеи, алгоритм их написания очень не сложный и рекомендован для самостоятельной проработки.

Метод сортировки пузырьками в ряде литературных источников называют еще методом прямого обмена.

Основная идея, заложенная в методе, известном как сортировка пузырьками, состоит в следующем. При каждом прохождении через список первый ключ сравнивается со вторым и меньший ставится на первое место. Второй ключ сравнивается с третьем и меньший ставится на второе место. Эта процедура продолжается до тех пор, пока не будет обработан весь список. Затем совершается второй, третий проходы, пока мы наконец не сделаем проход, при котором не будет ни одной перестановки, т.е. все ключи останутся на месте. Теперь список отсортирован.

Аналогично строится сортировка, когда элементы необходимо расположить в порядке убывания, только в этом случае, после сравнения в левую сторону будут уходить элементы, имеющие большие значения.

Метода отыскания наименьшего (наибольшего) ключа часто называют методом прямого выбора. Рассмотрим этот метод для группировки элементов по возрастанию, т.е. отыскания наименьшего ключа. Он основан на следующих принципах:

1. Выбирается элемент с наименьшим ключом.

2. Этот элемент меняется местами с первым элементом.

3. Затем этот процесс продолжается с оставшимися элементами до тех пор, пока не останется один, самый большой элемент.

Другими словами, существо данного метода состоит в том, что вначале отыскивается наименьший из всех элементов, и если он не первый, то ставиться на первое место, а элемент стоящий на первом месте ставится на место переставленного элемента. Затем из оставшегося списка отыскивается наименьший элемент, и если он не первый из оставшегося списка, то ставиться на второе место общей последовательности, а второй элемент на место переставленного элемента. Такая последовательность операций осуществляется до тех пор, пока не будет достигнут последний элемент. Таким образом сортируется список.

Метод прямого выбора противоположен в некотором смысле методу прямого включения. При прямом включении на каждом шаге рассматривается только один очередной элемент исходной последовательности, среди которых отыскивается точка включения; при прямом выборе для поиска одного элемента (например, наименьшего) просматриваются все элементы.

Данная ситуация рассмотрена когда элементы ставятся в порядке возрастания, аналогично строится сортировка, когда элементы необходимо расположить в порядке убывания, только в этом случае, после сравнения в левую сторону будут уходить элементы, имеющие большие значения.

6.3. Сортировка последовательностей.

В предыдущем разделе мы рассмотрели внутреннюю сортировку, которая проводилась для данных, размещенных в оперативной памяти ЭВМ, путем осуществления операций сравнения больших элементов с меньшими и их перемещений, а также обменов, обрабатывая элементы один за другим (не параллельно) и постепенно приводя последовательность к упорядоченной. В данном разделе рассмотрим сортировку, которая производится для последовательностей, хранящихся в файлах с последовательным доступом, расположенных на магнитных дисках или магнитных лентах. Отметим одну особенность, заданные последовательности обычно имеют объем больший, чем оперативная память, что влияет на алгоритм их сортировки.

Для выполнения внешней сортировки производятся следующие операции:

1. Находят нужный блок (или блоки) во внешней памяти.

2. Производят считывание этого блока (или блоков) в оперативную память, при этом суммарный размер блоков не должен превышать размер имеющейся оперативной памяти.

3. В оперативной памяти производятся операции сравнения и перемещения.

4. Затем вновь производится запись во внешнюю память.

Операции 1, 2, 3, 4 проводят несколько раз, выбирая блоки определенным образом, в итоге получают упорядоченную последовательность записанную во внешнюю память.

Поскольку операции, выполняемы в оперативной памяти для сортировки сравнительно просты, эффективность всей сортировки определяется в основном операциями ввода-вывода, время выполнения которых существенно больше. Именно в этом заключается в основном отличие внешней сортировки.

Рассмотрим более подробно сортировку одного большого файла, сформулируем алгоритм и пример.

Допустим имеется последовательность данных - последовательный файл, который не может быть целиком помещен в оперативную память и там обработан. Мы имеем доступ только к одному элементу этого файла, убрав который мы будем иметь доступ к следующему и так далее. Задача состоит в том, чтобы обработать такие данные, расположив их все по возрастанию.

1. Вначале этот файл разбивается на блоки.

Обычно разбиение осуществляется различным образом. Но принципы разбиения можно условно разделить на два противоположных правила.

А) Разбиение осуществляется таким образом, чтобы размер блока был как можно больше и но в тоже время он не превышал размеров оперативной памяти.

Б) Разбиение осуществляется таким образом, уже на стадии разбиения осуществлялась сортировка, при этом число блоков обычно бывает большое, но как правило все эти блоки могут помещаться в оперативную память.(Если они не помещаются в оперативную память то их искусственно разделяют).

2. Осуществляется сортировка внутри каждого блока.

Если разбиение осуществлялось по пути 1.Б, то данная операция не нужна.

3. Производится слияние файлов.

Одновременно открываются два или более файлов для ввода, и один файл для вывода. Данные в файл для вывода помещаются упорядоченным образом, т.е. сравниваются все открытые данные и помещаются в порядке возрастания.

Рассмотрим пример.

Имеется последовательность, которую необходимо упорядочить.

5 6 2 4 8 9 3 1 7

Разбивает ее на блоки или отрезки. Вначале пусть разбиение осуществляется по пути 1.А, т.е. если последующий элемент больше предыдущего, то оставляем этот элемент в данной последовательности, если нет, то открываем новую последовательность. В итоге имеем четыре последовательности из 2-х, 4-х, 1-ого и 2-х элементов

5 6 2 4 8 9 3 1 7

Записываем их в четыре разных файла. Сделаем замечание такого рода среднее число отрезков в произвольной последовательности из N элементов равно (N+1)/2. Доказательство этого утверждения здесь мы опустим, так как это непосредственно не является нашей целью.

Затем происходит слияние четырех файлов в один файл, каждый раз сравнивая четыре входных значения.

Первый выбор даст число 1 - в результирующем файле, и удаление первого элемента из четвертой последовательности

5 6

2 4 8 9 1

Первый выбор добавит число 2 - в результирующем файле, и удаление первого элемента из второй последовательности

5 6

4 8 9 2 1

Такой процесс будет осуществляться до тех пор пока не будет переставлен последний элемент. В итоге мы имеем результирующую упорядоченную последовательность.

9 8 7 6 5 4 3 2 1

Отметим, одну особенность данные в ней расположены по убыванию. Для того, чтобы они были расположены по возрастанию, можно либо переписать их в новую последовательность (тогда первый элемент последовательности (самый большой) записывается первым и, следовательно, становится последним в новой последовательности), либо разбиение и сравнение данных осуществлять противоположно изложенному методу, чтобы получилась возрастающая последовательность.

Данную операцию можно провести и таким образом

Разбиение осуществляется на два файла.

5 6 2 4 8 9 3 1 7

Эти файлы помещаются в оперативную память (вначале один потом другой) и сортируются, в итоге имеем

2 4 5 6 1 3 7 8 9

Затем осуществляется слияние файлов, имея два файла для выбора данных и один файл для ввода, в результате имеем

2 4 5 6 9 8 7 6 5 4 3 2 1

1 3 7 8 9

В этом примере мы аналогично пришли к убывающей последовательности, так как меньший элемент мы записывали в первую очередь и, следовательно, он становился последним в списке.

Существуют различные методы сортировки последовательностей, которые различаются в способе слияния, разбиения числе шагов разбиения и слияния, когда процессы разбиения и слияния повторяются многократно. Однако в данном учебном пособие мы ограничимся рассмотрением в принципе сортировки последовательностей, которое было приведено выше.

6.4. Поиск

Одно из наиболее часто встречающихся в программировании действий - это поиск. Он же представляет собой идеальную задачу, на которой можно испытывать различные структуры данных по мере их появления. При дальнейшем рассмотрении мы будем исходить из того допущения, что группа данных, в которых надо отыскать элемент, фиксирована и задача заключается в том, что надо найти элемент, который имеет определенный ключ. Так как нас интересует сам процесс поиска, а не обнаруженные данные, то будем считать, что мы ищем не ключ элемента, а сам элемент, из множества элементов, представляющих собой положительные числа.

Дата добавления: 2014-12-16