Поиск элемента

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

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

· Выбирается некоторый элемент, который называется опорным.

· Реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного – справа от него.

· Рекурсивно упорядочиваем массивы, лежащие слева и справа от опорного элемента.

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

void QuickSort(ref int[] Array, int Left, int Right)

{

// i и j – индексы границ разделяемого массива

int i = Left;

int j = Right;

// x – индекс опорного элемента

int x = Array[(Left + Right) / 2];

do

{

// Ищем элемент слева, который больше опорного

while (Array[i] < x)

++i;

// Ищем элемент справа, который меньше опорного

while (Array[j] > x)

--j;

// Если индексы не поменялись местами,

// то обмениваем элементы

if (i <= j)

{

int t = Array[i];

Array[i] = Array[j];

Array[j] = t;

i++;

j--;

}

} while (i <= j);

// Рекурсивно выполняем быструю сортировку

// для массивов слева и справа

if (Left < j)

QuickSort(ref Array, Left, j);

if (i < Right)

QuickSort(ref Array, i, Right);

}

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

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

// Простой поиск элемента в массиве

int IndexOf(ref int[] Array, int Value)

{

// Перебираем все элементы массива

for (int i = 0; i < Array.Length; i++)

// Нашли нужное значение? Возвращаем его индекс

if (Array[i] == Value)

return i;

// Перебор закончился безрезультатно – возвращаем -1

return -1;

}

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

Вычислительная сложность алгоритма простого поиска – линейная O(n).

Если массив упорядочен по возрастанию, то возможно использование дихотомического рекурсивного алгоритма: массив каждый раз делится пополам и если искомый элемент меньше среднего, то поиск продолжается в левой его половине, иначе – в правой:

// Дихотомический поиск элемента в массиве

static int IndexOf(ref int[] Array, int Value,

int Left, int Right)

{

// Находим середину диапазона

int x = (Left + Right) / 2;

// Если нашли значение – возвращаем его индекс

if (Array[x] == Value)

return x;

// Если середина совпадает с левой или

// правой границами – значение не найдено

if ((x == Left) || (x == Right))

return -1;

// Продолжаем поиск слева или справа от середины

if (Array[x] < Value)

return IndexOf(ref Array, Value, x, Right);

else

return IndexOf(ref Array, Value, Left, x);

}

Вычислительная сложность алгоритма – логарифмическая.

Индивидуальное задание

Общая часть задания: сформировать массив из 100 случайных чисел. Выполнить простой поиск элемента, подсчитать количество итераций. Отсортировать массив методом, указанным в своём варианте. Выполнить поиск элемента методом дихотомии, подсчитать количество итераций. Сделать выводы.

1. Метод пузырька

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

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

Лабораторная работа №15
Рекурсия

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

Дата добавления: 2014-11-07