Сортировка14.pdf Программирование

11 Центрированная сортировка

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

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

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

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

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

Этапы алгоритма:

1.Работаем с новым массивом, длина которого равна длине исходного, а значение каждого элемента равно нулю.

2.Определяем середину (позицию центрального элемента) всего массива (imed = n/2)

3.Указатели на начало и конец списка устанавливаются равными середине.

4.Значение среднему элементу приравниваем первое значение исходного массива и просмотр начинаем со второго элемента и до последнего.

5.если элемент исходного массива больше центрального элемента рабочего массива

a.тогда

-если указатель на конец списка равен последней позиции массива, то сдвигаем рабочий массив влево, указатель на первую позицию уменьшаем на единицу.

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

-указатель на последнюю позицию увеличиваем на единицу.

b.иначе

-если указатель на начало списка равен нулю, то сдвигаем рабочий массив вправо, указатель на последнюю позицию увеличиваем на единицу.

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

-указатель на последнюю позицию увеличиваем на единицу.

	11 Центрированная сортировка
		начало
		imed=n/2
		ximed =y0
		fp=lp=imed
		i=1;i<n; i++
	Да	Нет
		yi > ximed	Да
Да
	lp == n-1	fp == 0
q=fp--;q<n;			q=lp++;q≥0;
xq-1 = xq, q++			xq+1 = xq, q--
q			q
imed--; lp--			imed++; fp++
	p=++lp	p=--fp
	q=imed+1;	q=imed-1;
	q<lp; q++	q≥fp; q--
Да	yi < xq	yi > xq	Да
			k=fp; k<q;
k=lp; k>q;
xk = xk-1, k--			xk = xk+1, k++
k			k
p=k	q	q	p=k
		xp > yi
		i
		конец

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

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

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

Способ построения частей, по существу, один и тот же во всех версиях алгоритма. Устанавливаются два указателя, один на начало, другой на конец списка. После выбора основы поиск

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

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

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

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

На первом этапе строятся две части. Одна из них используется в качестве исходной на втором этапе, вторая помещается в стек LIFO. Общее правило таково: первой обрабатывать меньшую часть, а границы большей запоминать в стеке. Второй этап порождает две части. Меньшая обрабатывается на третьем этапе, а большая помещается в стек над большей частью, построенной на этапе 1. Процесс порождения частей, запоминания большей из них в стеке и разделения меньшей продолжается до тех пор, пока все части не сократятся до одного элемента. При возникновении одноэлементной части новая часть для стека не строится. Ожидающие части выбираются из стека и обрабатываются. Сортировка выполнена, когда стек пуст.

Этапы алгоритма:

1.Данный вид сортировки выполняется рекурсивно, т.е. функция при выполнении вызывавает саму себя, с параметрами равными значениям диапазона позиций элементов, которые нужно упорядочить, при первом вызове: 0 и номер последнего элемента списка.

2.Устанавливаются указатели на начало и конец рабочего списка и номер позиции основы (например, середина массива).

3.Процесс осуществляется пока указатель на начало списка меньше или равен указателю на конец списка.

4.Внутри этого процесса ищем элементы для обмена: с начала списка ищем элемент, больший основы, с конца – меньший основы, и если второй индекс больше первого осуществляем перестановку.

5.После окончания данного процесса выполняем алгоритм с п.2, в двух частях

a.В первой части, если начало диапазона просмотра при вызове меньше указателя на конец списка; и

b.Во второй части, если указатель на начало списка меньше конца диапазона просмотра.

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

начало

i=l; j=r

med=x(l+r)/2

xi < med

i++

i

xj > med

j--

j

Да

i ≤ j

temp=xi

xi++=xj

xj--=temp

i ≤ j

Да

l < j

sort12(l, j)

Да

i < r

sort12(i, r)

конец

13 Квадратичный выбор

Список разделяется N на частей. Если N не является точным квадратом, то

список разделяется на N

частей, где N есть ближайший точный квадрат,

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

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

Этапы алгоритма:

1. Массив, состоящий из m элементов, разбиваем на n m частей, если в результате извлечения корня получается не целое число и квадрат целой части этого числа меньше числа элементов в массиве, то увеличиваем целой части на 1 значение

(n=n+1).

2.Создаем вспомогательный массив b, состоящий из n элементов, в который мы будем записывать минимальные элементы каждой части.

3.Создаем выходной массив new1, состоящий из m элементов, с отсортированными элементами.

4.Запоминаем первые элементы частей и сравниваем с ними остальные элементы частей.

5.Запоминаем индексы минимальных элементов.

6.Заносим эти элементы в вспомогательный массив b, а в исходном массиве заменяем их большими фиктивными величинами.

7.Просматриваем вспомогательный массив b и находим в нем мин-ный элемент.

8.Помещаем его в выходной массив new1.

9.Запоминаем индекс той части, из которой был взят этот элемент.

10.Просматриваем эту часть и снова находим в ней минимальный элемент.

11.Заносим его в вспомогательный массив на место самого минимального.

12.В исходном массиве вновь заменяем этот элемент большой фиктивной величиной.

13.Просмотр продолжается до тех пор, пока все элементы в исходном массиве не будут заменены большими фиктивными величинами.

14.На экран выводится выходной массив new1 с отсортированными по возрастанию элементами.

13 Квадратичный выбор

начало

s,m,r,*b,*new1

m=sqrt(n)

Да

m2 < n

m++

b[m], new1[n]

t=0; t<m; t++

r = m * t

i=m*t+1;

i<m(t+1) &&

i<n; i++

Да

xi < xr

r = i

i

bt = xr ; xr =

30000

t

1

1

j=0; t<n; j++

r = 0

i=1; i<m; i++

Да

bi < br

r = i

i

new1j = br ;

s = m * r

t=m*t+1;

t<m(r+1) &&

t<n; t++

Да

xt < xs

s = t

t

br = xs ; xs =

30000

j

конец

14 Сортировка распределением

Область вывода делится на А «бункеров». А соответствует числу значений, которые могут принимать символы ключей. Если известно, что все символы ключей – числа по основанию 10, то А равно 10. Для каждого символа должен быть свой бункер, т.е. А равно размеру алфавита, используемого для построения ключей.

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

Этапы алгоритма:

1.Для сортировки целых десятичных чисел создаем массив b[n][10], где n- число элементов исходного массива, который и представляет собой 10 бункеров.

2.Также создаем массив с[10], который считает число элементов в каждом бункере, обнуляем его.

3.При первом просмотре расставляем числа по бункерам в соответствии с цифрой (p) единичного разряда (самого правого), при этом увеличивая счетчик элементов соответствующего бункера. После чего собираем элементы из бункеров начиная с меньшего (0).

4.Повторяем «распределения» и «собирания» для всех цифр (десятки, сотни и т.д.). То есть пока r не равно 0 (r-максимальное число массива). Обнуляем счетчик (c[]) перед каждым распределением.

5.После первых 4 этапов мы получаем массив целых чисел, упорядоченных по их модулю. Для перестановки отрицательных элементов в начало копируем массив a[] в массив d[]. В циклах сначала ставим отрицательные элементы в начало, затем все нулевые элементы, затем положительные элементы.

начало

ii=0

s=1; r!=0;

s++, r/=10

i=0; i<n;

i++, ci=0

i

i=0; i<n; i++

p=|ai|%10s/

10s-1;

b[c[p]][p]=ai;

cp++;

i

i=0, k=0;

k<10; k++

j=0; j<c[k];

j++

ai++=bik

j

k

r

1

1

i=0;i<n;i++

di=ai

i

i=n-1; i>=0;

i--

Да

di < 0

aii++=di

i

i=0; i<n; i++

di ==0

aii++=di

i

i=0; i<n; i++

di > 0

aii++=di

i

конец