Тема 10. Приемы программирования. Примеры алгоритмов

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

Задача сортировки ставится следующим способом. Пусть имеется массив целых или вещественных чисел a₁,...,a_n. Требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по неубыванию: а₁ ≤ a₂ ≤ ... ≤a_n или невозрастанию: а₁ ≥ a₂ ≥ ... ≥a_n. Если числа попарно различны, то говорят об упорядочении по возрастанию или убыванию. В дальнейшем будем рассматривать задачу упорядочения по неубыванию, т.к. остальные задачи решаются аналогично. Существует множество алгоритмов сортировки, каждый из которых имеет свои характеристики по скорости. Рассмотрим самые простые алгоритмы, в порядке увеличения скорости их работы.

Сортировка обменами (пузырьком)

Этот алгоритм считается самым простым и самым медленным. Шаг сортировки состоит в проходе снизу вверх по массиву. При этом просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то они меняются местами.

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

Исходный массив

0 15 8 10 19 20 6 16 5 19

	№ шага

1: 0 15 8 10 19 20 6 5 16 19

1: 0 15 8 10 19 20 5 6 16 19

1: 0 15 8 10 19 5 20 6 16 19

1: 0 15 8 10 5 19 20 6 16 19

1: 0 15 8 5 10 19 20 6 16 19

1: 0 15 5 8 10 19 20 6 16 19

1: 0 5 15 8 10 19 20 6 16 19

2: 0 5 15 8 10 19 6 20 16 19

2: 0 5 15 8 10 6 19 20 16 19

2: 0 5 15 8 6 10 19 20 16 19

2: 0 5 15 6 8 10 19 20 16 19

2: 0 5 6 15 8 10 19 20 16 19

3: 0 5 6 15 8 10 19 16 20 19

3: 0 5 6 15 8 10 16 19 20 19

3: 0 5 6 8 15 10 16 19 20 19

4: 0 5 6 8 15 10 16 19 19 20

4: 0 5 6 8 10 15 16 19 19 20

Результат

0 5 6 8 10 15 16 19 19 20

Рис. 37. Сортировка массива методом «пузырька»

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

//процедура сортировки обменами (пузырьком)

void SortBubble (int count, int* pArr)

{

int trash = 0;

for (int i = 0; i < count; i++) // i - номер прохода

{

for (int j=0; j < count-i-1; j++) // внутренний цикл прохода

{

if (pArr[j] > pArr[j+1]) //если "левый" больше "правого"

{

trash = pArr[j]; //меняем местами элементы

pArr[j] = pArr[j+1];

pArr[j+1] = trash;

}

}

}

}

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

Сортировка выбором выполняется несколько быстрее, чем сортировка методом пузырька. Алгоритм заключается в следующем: нужно найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать тоже самое, начав со второго элемента и т.д. Таким образом, создается отсортированная последовательность путем присоединения к ней одного элемента за другим в правильном порядке. На i-м шаге выбирается наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов изображена на рис.38.

Исходный массив

16 6 6 20 2 19 13 6 3 3

	№ шага

1: 2 6 6 20 16 19 13 6 3 3

2: 2 3 6 20 16 19 13 6 6 3

3: 2 3 3 20 16 19 13 6 6 6

4: 2 3 3 6 16 19 13 20 6 6

5: 2 3 3 6 6 19 13 20 16 6

6: 2 3 3 6 6 6 13 20 16 19

7: 2 3 3 6 6 6 13 20 16 19

8: 2 3 3 6 6 6 13 16 20 19

9: 2 3 3 6 6 6 13 16 19 20

10: 2 3 3 6 6 6 13 16 19 20

Результат

2 3 3 6 6 6 13 16 19 20

Рис. 38. Результат сортировки выбором

Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

//процедура сортировки выбором

void SortSelect(int count, int* pArr)

{

int i1,temp;

int jmax;

for (int i = count - 1; i > 0; i--) // i - номер текущего шага

{

jmax = 0;

for (int j = 0; j <= i; j++)

{

if (pArr [jmax] < pArr [j]) i1 = j;

}

temp = pArr [i1];

pArr [i1] = pArr [i];

pArr [i] = temp;

}}

Сортировка простыми вставками

Просматривается массив и каждый новый элемент a[i] вставляется на подходящее место в уже упорядоченную совокупность a[1],...,a[i-1]. Это место определяется последовательным сравнением a[i] с упорядоченными элементами a[1],...,a[i-1]. Таким образом в начале массива "вырастает" отсортированная последовательность.

Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[1]...a[i-1]стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[1]...a[i-1] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы.

Рассмотрим действия алгоритма на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[1]...a[i-1] и неупорядоченную a[i]...a[n].

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

Таким образом, в процессе вставки мы "просеиваем" элемент X к началу массива, останавливаясь в случае, когда

1. Hайден элемент, меньший X.

2. Достигнуто начало последовательности.

Исходный массив

№ шага

12 16 10 9 10 9 9 11 10 11

2: 12 16 10 9 10 9 9 11 10 11

3: 10 12 16 9 10 9 9 11 10 11

4: 9 10 12 16 10 9 9 11 10 11

5: 9 10 10 12 16 9 9 11 10 11

6: 9 9 10 10 12 16 9 11 10 11

7: 9 9 9 10 10 12 16 11 10 11

8: 9 9 9 10 10 11 12 16 10 11

9: 9 9 9 10 10 10 11 12 16 11

10: 9 9 9 10 10 10 11 11 12 16

Результат

9 9 9 10 10 10 11 11 12 16

Рис. 39. Сортировка массива простыми вставками

//процедура сортировки простыми вставками

void SortInsert (int count, int* pArr)

{

int temp, j;

for (int i = 1; i < n; i++) // цикл проходов, i - номер прохода

{

temp = pArr[i];

j = i-1; // поиск места элемента в готовой последовательности

while (j >= 0 && pArr[j] > temp)

{

pArr[j+1] = pArr[j]; // сдвигаем элемент направо, пока не дошли

--j;

}

// место найдено, вставить элемент

pArr[j+1] = temp;

}

}

Сортировка простыми вставками является наиболее быстрой из рассмотренных. На практике очень часто используются оптимизированные (улучшенные) алгоритмы сортировки на основе алгоритма простых вставок, например, алгоритм простых вставок со «сторожевым» элементом или алгоритм Шелла.

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

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

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