Алгоритм дихотомического поиска

⇐ ПредыдущаяСтр 5 из 6Следующая ⇒

Этот алгоритм является более быстрым, чем линейный, но применяетсятолько к упорядоченным массивам. Среднее время дихотомического поиска пропорционально величине log₂n, где n — количество элементов таблицы эталонов. Таким образом, ускорение достигается за счет дополнительной информации о расположении элементов, а асимптотическая оценка алгоритма О(n) = log₂n.

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

Общийалгоритм поиска будет таким же, как в п. 1.

1. Ввести исходный массив (ключей).

2. Повторять

ввести аргумент поиска и вывести результат

пока не надоест.

3. Закончить.

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

Уточненный алгоритм можно представить в следующем виде.

1.1. Ввести количество элементов массива (n).

1.2. Инициировать датчик случайных чисел.

1.3. Для номера элемента (i) от 0 до n

1.3.1. Вычислить ключ[i].

2. Упорядочить ключи по возрастанию:

2.1. Для номера просмотра (k) от 1 до n - 1

2.1.1. Для номера слова (i) от 0 до n - k

Если ключ [i] > ключ [i+1],

поменять местами ключ[i] и ключ[i+1].

3. Выполнять

3. 1. Ввести аргумент поиска (целое число);

3. 2. Если аргумент поиска больше или равен нулю,

3.2.1 Граница_левая (диапазона поиска) = 0;

3.2.2. Граница_правая (диапазона поиска) = n - 1 (Длина.массива – 1);

3.2.3. Если аргумент поиска = ключ [n - 1],

a) Признак = «Найдено»;

b) k = n – 1.

Иначе

3.2.4. Признак = «Не найдено».

3.2.5. Выполнять

a) Номер аргумент поиска (k) = Целое ((Граница_левая + Граница_правая)/2);

b) Если аргумент поиска = ключ [k],

Признак: = «Найдено»

Иначе

Если аргумент поиска > ключ [k],

Граница_левая = k

Иначе

Граница_правая = k.

Пока не «Найдено» Или (Граница_левая = Граница_правая - 1).

3.3. Если «Найдено»,

вывести: «Ключ найден под номером k»,

Иначе

вывести: «Такого ключа в массиве нет».

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

4. Закончить.

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

Будем использовать те же обозначения переменных, что и для линейного поиска. Значения ключей получим как случайные числа из диапазона от 0 до 99. Фрагмент программы дихотомического поиска, соответствующая приведенному выше алгоритму, будет иметь вид.

public static void main (String[] args) {

Scanner sc=new Scanner(System.in);

int n;

System.out.print(" Введите количество элементов массива => " );

n=sc.nextInt();

System.out.println(" \tВведите элементы массива " );

int key[]=new int[n];

Random rn=new Random();

for (int i = 0; i < key.length; i++)

key[i]=rn.nextInt(100);

System.out.println(" \n Поиск ключа" );

int lev, prav, k;

boolean naideno;

do{

int arg, num;

System.out.println(" \n Введите аргумент поиска – искомый ключ" );

arg=sc.nextInt();

if (arg> =0){

num=-1;

if arg==key[n-1] {

k=n-1;

naideno=true;

}

else {

naideno=false;

do {

k=(int)((lev+prav)/2);

if (arg==key[k])

naideno=true;

else

if (arg> key[k])

lev= k;

else

prav= k;

} while (naideno || (lev==prav-1));

}

if (naideno)

System.out.println(" Ключ найден, его номер " + k);

else

System.out.println(" Такого ключа нет" );

} while (arg> =0);

}

АЛГОРИТМЫ СОРТИРОВКИ

3.1. Основные определения и классы алгоритмов

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

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

1.1.1. Классификация алгоритмов сортировки

При классификации учитывают следующие основные характеристики алгоритмов.

1) Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.

1) Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту особенность входной последовательности и работает лучше.

2) Использование операции сравнения. Алгоритмы, применяющие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n²), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является сфера его применения. При этом различают два основных типа упорядочения.

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

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

К алгоритмам устойчивой сортировки относят следующие.

1. Сортировка пузырьком (англ. Bubble sort ) — сложность алгоритма: O(n²); для каждой пары индексов производится обмен, если элементы расположены не по порядку.

2. Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — сложность алгоритма: O(n²).

3. Сортировка вставками (Insertion sort) — сложность алгоритма: O(n²); определяют место элемента в упорядоченном списке и вставляют его туда.

4. Гномья сортировка — сложность алгоритма: O(n²); сочетает методы пузырьковой сортировки и вставками.

5. Блочная сортировка (Корзинная, Bucket sort) — сложность алгоритма: O(n); требуется O(k) дополнительной памяти и знание о природе сортируемых данных.

6. Сортировка подсчётом (Counting sort) — сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти (существует три варианта).

7. Сортировка слиянием (Merge sort) — сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; упорядочивают две половины списка отдельно (первую и вторую), а затем — сливают их воедино.

8. Сортировка с помощью двоичного дерева (англ. Tree sort) — сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти.

Алгоритмами неустойчивой сортировки являются следующие методы.

1. Сортировка выбором (Selection sort) — сложность алгоритма: O(n²); выполняется поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка.

2. Сортировка Шелла (Shell sort) — сложность алгоритма: O(n log₂ n); попытка улучшить сортировку вставками.

3. Сортировка расчёской (Comb sort) — сложность алгоритма: O(n log n)

4. Пирамидальная сортировка (Сортировка кучи, Heapsort) — сложность алгоритма: O(n log n); список превращается в кучу, берется наибольший элемент и добавляется в конец списка.

5. Плавная сортировка (Smoothsort) — сложность алгоритма: O(n log n).

6. Быстрая сортировка (Quicksort), в варианте с минимальными затратами памяти сложность алгоритма: O(n log n) — среднее время, O(n²) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; исходный набор данных разбивается на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй; затем алгоритм применяется рекурсивно к каждой половине. При использовании O(n) дополнительной памяти сортировка становится устойчивой.

7. Поразрядная сортировка — сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.

8. Сортировка перестановкой — O(n·n! ) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.

Рассмотрим наиболее распространенные алгоритмы сортировки. Причем, запишем словесные пошаговые алгоритмы, а программы составим на лабораторных работах.

1.2. Наиболее распространенные
простые алгоритмы внутренней сортировки (массивов)

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

a[0], a[1], a[2], … a[n-1].

Их можно разделить на три основные категории:

1) Сортировка вставками;

2) Сортировка выбором и

3) Сортировка обменом.

1.2.1. Сортировка вставками

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

Рассмотрим работу алгоритма на примере массива из 8 чисел.

Исходный массив 44 55 12 42 94 18 06 67

При i = 1 44 55 12 42 94 18 06 67

При i = 2 12 44 55 42 94 18 06 67

При i = 3 12 42 44 55 94 18 06 67

При i = 4 12 42 44 55 94 18 06 67

При i = 5 12 18 42 44 55 94 06 67

При i = 6 0612 18 42 44 55 94 67

При i = 7 0612 18 42 44 55 6794

Здесь последний элемент подмассива (с последним значением j) выделен жирным, а анализируемый элемент – подчеркнут.

Словесное описание алгоритма можно представить так.

Алгоритм простой сортировки вставками

1. Задать исходный массив А из n элементов.

2. Для i от 0 до n

2.1. Индекс элемента в конце массива j = i

2.2. Пока (j > 0) И (А_j_-₁ > A_i)

2.2.1. Сдвиг большего элемента, чтобы было место для вставки

А_j = А_j-₁

2.2.2. j = j - 1

2.3. Вставка j - го элемента на его место

А_j = A_i

3. Вывести массив А.

Число сравнений и пересылок в худшем случае пропорционально n², т.е. сложность алгоритма равна О(n²).

Время сортировки можно сократить, если учесть, что начальная часть массива (до индекса j) упорядочена. При этом точку вставки можно найти методом деления пополам диапазона индексов этой части (от 0 до j).

Алгоритм сортировки двоичными вставками

4. Задать исходный массив А из n элементов.

5. Для i от 0 до n

5.1. Вставляемый элемент х = A_i

5.2. Левая граница диапазона L = 0.

5.3. Правая граница диапазона R =i.

5.4. Пока (L< R)

5.4.1. Искомый индекс m = (L + R)/2

5.4.2. Если A_m ≤ x

L = m + 1

Иначе

R = m.

5.5. Перепись элементов на одну позицию в конец массива (освобождение места для вставки)

Для j от i до R + 1 с шагом -1

А_j = А_j-₁

5.6. Вставка последнего элемента

А_R= x

6. Вывести массив А.

Число сравнений и пересылок рассмотренным методом в худшем случае пропорционально n*log(n), т.е. сложность алгоритма равна О(n*log(n)).

1.2.2. Сортировка выбором

Этот метод – один из наиболее простых. Он требует выполнения n-1 просмотра массива. Вначале выбирают наименьший элемент и ставят его на место первого элемента массива. Эта операция выполняется для оставшихся n-1 ключей, затем – для (n-2)-х и т. д. Во время k-го просмотра выявляется наименьший элемент, который затем меняется местами с k-м.

Рассмотрим работу алгоритма на примере массива из 8 чисел, использованного в предыдущем примере.

Исходный массив 44 55 12 42 94 18 06 67

При i = 1 06 55 12 42 94 18 44 67

При i = 2 06 12 55 42 94 18 44 67

При i = 3 06 12 18 42 94 55 44 67

При i = 4 06 12 18 42 94 55 44 67

При i = 5 06 12 18 42 44 55 94 67

При i = 6 06 12 18 42 44 55 94 67

При i = 7 0612 18 42 44 55 6794

Здесь начальный элемент подмассива, в котором ищется минимум, выделен жирным, а минимальное значение в нем – подчеркнуто.

Алгоритм сортировки выбором

1. Задать массив А из n чисел.

2. Для k от0 до n-1

2.1. j = k

2.2. Для i от k + 1 до n-1

2.2.1. Если A_i< A_j,

j = i.

2.3. Если k ≠ j, то

Поменять местами A_k и A_j.

3. Вывести массив A.

4. Закончить.

Число сравнений и пересылок в худшем случае пропорционально n², т.е. сложность алгоритма равна О(n²), а в среднем - О(n*log(n)). Таким образом, сортировка выбором предпочтительнее метода вставок.

3.2.3. Сортировка обменом
(Пузырьковая сортировка)

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

1) элементы массива сравниваются попарно: первое со вторым; второе с третьим; i-тое – с (i+1) - вым;

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

За один такой просмотр массива при сортировке по возрастанию минимальный элемент «вытолкнется», по крайней мере, на одно место вверх (вперед), а максимальный – переместится в самый конец (вниз). Таким образом, минимальный элемент как легкий пузырек воздуха в жидкости постепенно «всплывает» вверх (в начало последовательности). Отсюда – название метода.

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

Исходный массив 44 55 12 42 94 18 06 67

После просмотра 1 44 12 42 55 18 06 67 94

После просмотра 2 12 42 44 18 06 55 67 94

После просмотра 3 12 42 18 06 44 55 67 94

После просмотра 4 12 18 06 42 44 55 67 94

После просмотра 5 12 06 18 42 44 55 67 94

После просмотра 6 06 12 18 42 44 55 67 94

Из примера видно, что большие числа сразу оказываются на своем месте, т.е. глубину просмотра можно уменьшать, а индекс элемента изменять не до n-1, а до n - k. В нем последние числа, которые стоят на своем месте, выделены жирным шрифтом.

За n-1 просмотр произойдет полное упорядочение массива при любом исходном расположении элементов в нем.

⇐ Предыдущая 1 2 3 456 Следующая ⇒