Основы программирования. Файлы. Рекурсия - 30 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

32
первой и второй части было примерно одинаковым (в идеале отличалось бы на 1 –
в этом случае элемент
x называется медианой массива). Однако, поиск медианы
массива – достаточно долгий алгоритм, поэтому обычно в качестве элемента
x
выбирают любой элемент массива, например, средний.
Рассмотрим алгоритм подробнее. После выбора опорного элемента x введем
два индекса
i и j, указывающие соответственно на первый и последний элементы
массива A. Увеличивая
i, найдем элемент A[i], не меньший x. Затем, уменьшая
j, найдем элемент A[j], не больший x. Такие элементы всегда найдутся: в крайнем
случае, таким элементом будет сам элемент
х. Поменяем элементы A[i] и A[j]
местами, после чего увеличим
i на 1 и уменьшим j на 1. Продолжим эти действия
до тех пор, пока i не окажется больше j. В этот момент все элементы
A[1]..A[j]
меньше или равны x, а все элементы A[i]..A[n] - больше или равны x. Теперь
применим наш алгоритм рекурсивно к подмассивам
A[1]..A[j] и A[i]..A[n].
Процесс рекурсивных вызовов прекращается, если подмассив состоит из одного
элемента.
Рассмотрим конкретный пример. Пусть массив
A размера n=9 имеет вид:
2 7 6 9 4 5 8 3 1
i j
Выберем в качестве
x средний элемент A[5]=4 и положим i=1, j=n. Увели-
чивая
i, найдем элемент A[i]>=x (это элемент A[2]=7) и уменьшая j найдем
элемент
A[j]<=x (это элемент A[9]=1).
2 7 6 9 4 5 8 3 1
i j
Поменяем их местами и передвинем индексы
i и j соответственно вперед и
назад:
2 1 6 9 4 5 8 3 7
i j
Аналогично поменяем местами элементы 6 и 3, затем 9 и 4. В результате ин-
декс
i станет больше индекса j:
2 1 3 4 9 5 8 6 7
j i
Следует обратить внимание на то, что
i может быть больше j на 1 или на 2, а
также на то, что опорный элемент в преобразованном массиве может поменять
свое место.
Итак, мы разделили массив на две части. Часть элементов с номерами от 1 до
j меньше или равна x, а часть элементов с номерами от j до n – больше или равна
x. Осталось рекурсивно применить алгоритм быстрой сортировки к обеим частям.
Ниже приводится код алгоритма:

Страницы