Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Сортировка фон Неймана (слиянием)






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

 

Пирамидальная сортировка:

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

Если в исходном массиве n элементов, то последние (n / 2) элемента становятся основанием пирамиды (эти элементы являются листьями дерева, т.е. у них нет потомков, поэтому для них вышеуказанное правило выполняется автоматически).

Удобнее всего поместить пирамиду в массив. При этом распределение индексов массива по узлам дерева будет выглядеть так (на этом рисунке все цифры - это индексы элементов массива, а ни в коем случае не значения этих элементов):

Таким образом, для того, чтобы каждый узел дерева был больше своих потомков, каждый элемент массива a[i] должен быть больше или равен элементам a[2 * i + 1] и a[2 * i + 2].

2. Сортировка
В этой части алгоритма мы перемещаем в конец массива максимальный элемент, затем исключаем его из дальнейшего процесса сортировки. Поскольку максимальный элемент всегда находится на вершине пирамиды, мы должны поменять местами элементы a[0] и a[n-1] (т.е. последний элемент). Причем элемент a[n-1] необходимо добавлять так, чтобы не нарушился порядок пирамиды (при этом пирамиду придется частично перестроить). Далее мы будем рассматривать массив только до (n-2)-го элемента.
На следующем шаге мы меняем местами a[0] и a[n-2] и далее рассматриваем массив только до (n-3)-го элемента. Повторяем всю эту процедуру до тех пор, пока в рассматриваемой части массива не останется один элемент.

Шейкер сортировка:

Это модификация метода «пузырька», которая учитывает два дополнительных требования:

1) устранение «лишних» просмотров массива, т.е. если массив уже отсортирован за первые проходы, последующие проходы не делаем. Пример: 12, 3, 5, 7, 9, 10.

2) смена направлений прохода массива: сначала проходим от начала к концу, по том – от конца к началу, потом снова от начала к концу и т.д. Это позволяет уменьшить число проходов по массиву. Пример: 5, 7, 9, 10, 12, 3.

 

Сортировка подсчетом:

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

Используются следующие обозначения:
A[1..n] - входная последовательность;
C[1..k] - вспомогательный массив из k элементов;
B[1..n] - выходная отсортированная последовательность.

Работа алгоритма заключается в следующем.
В элемент C[i] заносится количество элементов массива A, равных i.
Затем находятся частичные суммы последовательности C[1], C[2],..., C[k], каждая из которых является количеством элементов, не превосходящих i.
После этого каждый элемент A[i] из входного массива помещается в выходной массив B на позицию, равную значению элемента С[A[i]].

 

Цифровая сортировка:

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

 

 

17) Методы поиска: линейный поиск, метод бинарного писка, поиск с помощью бинарного дерева, метод случайного поиска.

 

Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.

 

Бинарный поиск –

Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.

Переменные Lb и Ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Поиск с помощью бинарного дерева

Если дерево пусто, сообщить, что узел не найден, и остановиться.

Иначе сравнить K со значением ключа корневого узла X.

 

· Если K=X, выдать ссылку на этот узел и остановиться.

· Если K> X, рекурсивно искать ключ K в правом поддереве Т.

· Если K< X, рекурсивно искать ключ K в левом поддереве Т.

 

Случайный поиск

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

 

Метод крайне не эффективен.

 

 

18) Алгоритмы внешней сортировки: метод естественного слияния, метод сбалансированного слияния. Двухпутевая и многопутевая реализация. Фибоначчиева сортировка.

 

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

 

Очевидно, что любой алгоритм сортировки файла требует изъятия каких-то

элементов из файла и включения их в файл на новые места. Таким образом, часть файла

должна быть переписана на новое место (в новый файл или несколько новых файлов), а

затем эти новые файлы должны быть объединены (слиты). Основным понятием будем

считать понятие отрезка файла. Отрезком длины k является последовательность записей

A i, A i+1, …A i+k-1 такая, что в ней все записи упорядочены по заданному ключу key.

 

Естественное слияние

При использовании метода прямого слияния не принимается во внимание то, что

исходный файл может быть частично отсортированным.

 

Первая серия упорядоченных записей и переписывается в файл B, вторая - в файл C

и т.д. При слиянии первая серия записей файла B сливается с первой серией файла C,

вторая серия B со второй серией C и т.д. Если просмотр одного файла заканчивается

раньше, чем просмотр другого (по причине разного числа серий), то остаток файла

целиком копируется в конец файла A. Процесс завершается, когда в файле A остается

только одна серия

 

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.