Алгоритмы поиска: последовательный, двоичный, метод золотого сечения, интерполяционный.

а)Последовательный

1)i=1

2)Смотрим i-й элемент. То, что нужно?

3)Если нет то i=i+1 и возвращаемся к пунтку 2

Время работы последовательного поиска пропорционально длинне самого массива, предварительная сортировка не обязательна.

б)Двоичный:

Проверяем средний элемент, если не подходит, то отбрасываем половину массива..

Проверяем средний элемент в оставшейся половине, если не подходит то отбрасываем половину от оставшихся…

в)Метод золотого сечения:

f(x):[a;b]→min, f(x)ϵC([a;b])

Делим отрезорк двумя симметричными точками и вычисляем в них функцию.

Отбрасываем тот отрезок Где значение функции максимально по модулю

На оставшемся отрезке нужно добавить только одну точку

Продолжаем…

 

 

 

г) Интерполирующий

Public int interpolationSearch (int [] SortedArray, int toFind) {

//Возвращает индекс элемента со значением toFind

//иначе возвращает -1

Int mid;

Int low=0;

Int high = SortedArray.Length-1;

While (sortedArray[low]<toFind && sortedArray[high]>toFind) {

Mid = low + ((toFind – sortedArray[low])*(high-low))/(sortedArray[high]-sortedArray[low])

If (sortedArray[mid]<toFind)

Low =mid+1;

Else if(sortedArray[mid>toFind])

High=mid-1;

Else return mid;

}

If (sortedArray[low]==toFind)

Return low;

Else if (sortedArray[high]==toFind)

Return high;

Else return -1;

}

 

Алгоритмическая сложность в среднем O(log(log N))

В худшем случае O(N)

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

 

Сортировки: пузырьковая, расчёской.

 

1)Пузырьковая:

В сортировке пузырьком, когда сравниваются два элемента, промежуток (расстояние друг от друга) равен 1.

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

 

Сортировка расчёской

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

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

 

Void sort (data* array, dword size) {

Dword jump = size;

Bool swapped = =true;

While (jump>1 || swapped)

{

If(jump > 1)

Jump = (dword)(jump/1.25);

Swapped = false;

For (dword i =0; i+jump < size; i++)

If (array[i] > array[i+jump])

Swap(array,i,i+jump), swapped = true }

}

 

 

 

Сортировка слиянием.

Для решения задачи сортировки эти три этапа выглядят так:

Сортируемый массив разбивается на две части примерно одинакового размера;

Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;

Два упорядоченных массива половинного размера соединяются в один.

 

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

 

2.1 Cоединение двух упорядоченных массивов в один.

Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два подмассива. Пусть также, элементы подмассивов в каждом из этих подмассивов отсортированы по возрастанию. Тогда:

2.2. Слияние двух подмассивов в третий результирующий массив.

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

2.3. "Прицепление" остатка.

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

 

Быстрая сортировка.

Быстрая сортировка часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

Краткое описание алгоритма:

1)выбрать элемент, называемый опорным.

2)сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.

3)повторить рекурсивно для «меньших» и «больших».

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

/* сортирует v[0]..v[n-1] по возрастанию */

Void quicksort (int v[], int n)

{

Int i, last;

If (n <= 1) //ничего не делать

Return;

Swap (v,0,rand()%n);//разделить

Last=0;

For (i=1; i<n; i++)

If (v[i] < v[0])

Swap(v,++last,i);

Swap(v,0,last) //сохранить разделитель

Quicksort (v,last); //рекурсивно отсортировать

Quicksort (v+last+1,n-last-1)//каждую часть}