Давыдов В.Г. - Программирование и основы алгоритмизации - 2003

±f(

arr[

к

] , key

>

max. key

)

(

indmax

=

k;

max

=

arrf

к

];

}

}

//

Поменять

местами

arr[

indmax

]

]

и arrf

L ]

arrf

indmax

]

= arrf

L

];

arrf

L

=

max;

}

)

return;

//

Сортировка

массива

простыми

включениями

-

по

неубыванию

void

InsertSort(

]

)

//

Сортируемый

массив

ELEMENT

arrlf

{

//

Используются

следующие

глобальные

объекты:

//

i

-

индекс

вставляемого

элемента;

сегменте;

//

J

-

индекс

элемента

в

упорядоченном

//

сору

= arrf

i

]

//

Перебор

вставляемых

элементов

£ог(

i=2;

1

<= size;

i++

)

{

copy

=

arrlf

1

];

arrlf

0

]

=

copy;//

Установка

"барьера"

//

Вставка

copy

на нужное

место

j =

i-1

;

while(

copy.key

<

arrlf

j

J.key

)

{

//

Сдвиг

arrlf

j+1 ] =

arrlf

j

];

j

-

-

;

}

arrlf

j+1

]

=

copy;

}

}

return;

//

Сортировка

массива

простым обменом

- по

неубыванию

(метод

//"пузырька")

void. BubbleSort	(	//	Сортируемый		массив
ELEMENT	arrf ] )
{	к;	//	Индекс анализируемого			элемента
int
ELEMENT	temp;	//	Для	перестановки		элементов
int	sorted^	//	1=0	(отсортирован)
	change;	//	!=0	(были	перестановки)

240

sorted = О;

//Цикл проходов

while

(

!sorted

)

{

change

=

О;

fori

к

=

1;

к

< size;

к++

)

{

±f(

arr[

k-1

].key

>

arr[

к

].key

)

{

temp

= arr[

к

];

arr[

к

J =

arr[

k-1 J;

arr/"

k-1

] =

temp;

change

=

1;

}

}

sorted

=

!change;

}

retvum;

}

//

Сортировка

массива

сложным

выбором

с

использованием

//

пирамиды

-

двоичного

дерева

//

Sift(

Просеивание

void

rooty

//

Корень

дерева

или

поддерева

Int

у

Int

last

)

//

Последняя

вершина

в

дереве

ELEMENT

arr[

]

//

Сортируемый

массив

{

// 1

-

позиция

"дырки"

(объект

определен

на

внешнем

//уровне)

Int	j l ,	//	j1	=	2*1	и	--	следующая		вершина
	j2;	//	j2	снизу			слева		для i	вершина
		//		=	2*1 + 1 -			следующая
// j	- претендент	//	и	снизу		и	справа		для	1
		из jl		j2	на	заполнение			"дыры"

//	(объект определен		на внешнем		уровне)	на
//	сору - просеиваемый		элемент	(объект	определен
//	внешнем	уровне)		место	для вставки	сору)
Int	found;	//	1 (нашли

//Подготовка

сору	=	агг[	root-1	];	1	=	root;	found =	0;
while	(	.'found	)
{	//	Определение		jl	и	j2	для зафиксированного			i
	jl	= 2*i;	j2	-	jl-hl;
	//	Анализ	вариантов			заполнения		"дыры"
	lf(	jl > last		)	//	Следующего уровня			внизу	нет
	{	found	=	1;

}

241

etlse

{

//

Следующий

внизу

уровень

есть

±£(

jl

==

last

)

{

J

}

= Jl/

else

{

j

=

(

arrf

J1-1

J.key

>= arrf

j2-l

] . key )

?

jl

:

j2;

}

Выяснение,

кто

заполняет

"дыру"

//

±f(

arr[

j-1

],key

<=

copy.key

)

{

found

=

1;

}

else

{

arr[

i-1

]

=

arr[

j-1

];

i=j;

}

}

}

arrf i-1 ]

=

copy;

return;

}

//

(

Сортировка

void TreeSort

arrf

])

//

Сортируемый

массив

ELEMENT

{

temproot,

//

Индекс

корня

частичного

поддерева

±nt

templast;

//

Последний

элемент

в

ELEMENT

tempcopy;

//

неупорядоченном

поддереве

//

Для

перестановки

элементов

//

Начальная

подготовка

дерева

for(

temproot

= size/2;

temproot

>

0;

temproot--

)

{

Sift(

temproot,

size,

arr

) ;

,^

//Сортировка

for(

templast

= size;

templast

>= 2; templast--

)

{

// Переставить максимум из корня дерева на

//окончательное место

tempcopy		=	arrf	О	];	arrf	О	] = arrf	templast-1	];
arrf	templast-1			]	=	tempcopy;
//	Просеять		новый		корень		на	место -	восстановить

//дерево

Sift(

1, templast-1,

arr ) ;

242

}

xretuxm/

}

// Сложная

сортировка

массива

вставками

(метод

Шелла)

void

ShellSort

(

ELEMENT

arr[

]

)

//

Сортируемый

массив

{

d,

//

izit

Дистанция

Шелла

fillpos;

//

Местоположение

"дыры"

//

i

-

индекс

анализируемого

элемента

(объект

определен

//

на

внешнем

уровне)

//

J

-

индекс

претендента

слева

на

заполнение

"дыры"

//

(объект

определен

на внешнем

уровне)

//

сору

=

arrfi]

(объект

определен

на

внешнем

уровне)

int

found;

//

1 (нашли

место

для

вставки

сору)

d

=

size;

while

(

d >

1

)

{

d

=

d/2;

//

Отсортировать

вставками

при

текущем

d

£or(

1

=

d;

i

< size;

i++ )

(

copy

= arr[

1

];

fillpos

=

i ;

//

Найти

место

вставки

copy

found

=

0;

do

{.

j =

fillpos

-

d;

±f(

j <

0 )

{

//

Претендента

слева

нет

found

=

1;

}

else

{

//

Претендент

слева

больше

-

сдвиг

if(

arr[

j

].key

<=

copy,key

)

{

}

found

=

1;

else

{

arr[

fillpos

] =

arr[

j

];

fillpos

^

j ;

}

}

}

while(

!found

)

;

//

Вставка

copy

arrf

fillpos

]

=

copy;

243

retuxm/

}
// Быстрая	сортировка		Хоора		- нерекурсивный			вариант
//	Занесение			в	стек	сегментов
void. Push (
±пЬ	left^		//	Левая граница			сегмента
int	rights		//	Правая		граница	сегмента
STACK	s[	7/	// Стек границ				сегментов
int	&sp	)	//	sp	- указатель		вершины стека

{

// В стек заносятся только сегменты из двух или более

//элементов

±f( ( right-left	) >= 1 )
{
sp+ + / s[	sp ],1 = left; s[ sp J.r = right/
}

return;

}

//

//

Извлчение

сегмента

из

стека

void

Pop (

&i,

// Указатель

int

на

левую

границу

int

&r,

//

сегмента

// Указатель

на

правую

границу

//

сегмента

STACK

s[

],

//

Стек границ

сегментов

(

int

&sp

)

//

Указатель

вершины

стека

1

= s[

sp

J.l;

г = s[

sp ].r;

sp--;

re

trim;

}

//

//

Быстрая

сортировка

массива

- нерекурсивный

вариант

void

Quicksort(

ELEMENT

arr[

] )

//

Сортируемый

массив

{

int

left,

//

Левая

граница

разделяемого

//

сегмента

right;

//

Правая граница

разделяемого

//

сегмента

//

i

-

индекс

кандидата

на

обмен

слева

-

направо

(объект

//

определен

на

внешнем

уровне)

//

j

-

индекс

кандидата

на

обмен

справа

-

налево

(объект

//

определен

на

внешнем

уровне)

//

median

- медиана

разделяемого

сегмента

(объект

244

//	определен на внешнем уровне)
//	сору - для перестановки кандидатов (объект определен

//на внешнем уровне)

STACK		s[ М ];	//	Стек границ	сегментов
±Tib		sp;	//	Указатель вершины стека
sp = -1 ;			//	Вначале стек	пуст
Push (	О,	size-lr S,	sp	);
while	( sp	>= О )

{

// Подготовка верхнего сегмента из стека для

//разделения

Pop (	left, right	г s , sp	);
median = arr[ (		left+rlght	)/2 ]; i = left;
J =	right;

//Разделение текущего сегмента

while ( 1 <= J )

{

//Найти кандидата на обмен слева

while ( arr[ i ].key < median.key ) i + + ;

//Найти кандидата на обмен справа

while ( median.key < arr[ j ],key ) j - - ;

// Обмен, если кандидаты находятся в разных

//подсегментах

if( 1 <= j		)
{
copy	= arr[ 1 ];		arr[ i ] = arr[ j ];
arr[	j	] = copy;	1++; j - - ;
I

}

// Поместить в стек сначала белее длинный подсегмент,

//а затем - более короткий

if( ( j-left		)	<	( right-1			) )
{			//	Леваый подсегмент				-	короче
Push	(	1,	right,		s ,	sp	);
Push	(	left,		J,	s ,	sp	);
}
else
{			//	Правый подсегмент				-	короче
Push	(	left,		J,	s ,	sp	);
Push	(	1,	right,		s ,	sp	);

}

}

return;

}

//Быстрая сортировка Хоора - рекурсивный вариант

void Quicksort 1 ( void )

245

(

Split	( Or size-1	);
return;
}
//
//	Функция разделения сегментов
void Split	(
±nt	leftr	//	Левая граница сегмента
int	right )	//	Правая граница сегмента
{
xf( ( right-left		) <=	О )

(

return;

}

else

(

// Подготовка

median = arr[ ( left + right )/2 ]; i = left;

j= ri gh t;

//Разделение

while( i <= j ) f

//Найти кандидата на обмен слева

while ( arr[ i ].key < median.key ) i + + ;

//Найти кандидата на обмен справа

while ( median.key < arrf j J.key ) j - - ;

// Обменr если кандидаты находятся в разных

//подсегментах

if( i <= J	)
I
copy = arrf 1 J;		arrf	i ] = arrf j ];
arrf J	] = copy;	i++;	j - - ;

}

}

//Финал - разделить сначала более короткий сегмент

if( ( j-left

) < ( rlght-1 ) )

{// Леваый сегмент - короче

Split ( leftr J ); Split ( 1, right );

}

else

I // Правый сегмент - короче Split ( 1, right ); Split ( left, j );

}

}

return;

Для файла данных, приведенного ниже.

246

44	55	12	42	94	18	6	61
файл результатов имеет следующий вид:
		Сортировка			массива		простым			выбором.		Массив		до		сортировки
		44			55			12			42			94		18
		6			61	Массив		после			сортировки
		6			12			18			42			44		55
		61			94
	Сортировка,			массива		простыми			включениями.				Массив		до	сортировки
		44			55			12			42			94		18
		6			61	Массив		после			сортировки
		6			12			18			42			44		55
		61			94
		Сортировка			массива		методом		"пузырька".			Массив			до	сортировки
		44			55			12			42			94		18
		6			61	Массив		после			сортировки
		6			12			18			42			44		55
		61			94
		Сортировка			массива		сложным			выбором.		Массив		до		сортировки
		44			55			12			42			94		18
		6			61	Массив		после			сортировки
		6			12			18			42			44		55
		61			94
		Сортировка			массива		методом			Шелла.		Массив		до	сортировки
		44			55			12			42			94		18
		6			61	Массив		после			сортировки
		6			12			18			42			44		55
		61			94
		Сортировка			массива		методом			Хоора.		Массив		до	сортировки
		44			55			12			42			94		18
		6			61	Массив		после			сортировки
		6			12			18			42			44		55
		61			94
		Рекурсивная				сортировка			Хоора.		Массив		до	сортировки			\
		44			55			12			42			94		18
		6			61	Массив		после			сортировки
		6			12			18			42			44		55	1
		61			94
		В приведенной программе на данном этапе заслуживают также
внимания следующие решения.
		1. Размещение				сортируемого					массива		в динамической				памяти

иосвобождение динамической памяти.

2.Механизм передачи сортируемого массива в функции сор­ тировок.

247

3. Оформление включаемого файла программного проекта.

Эффективность сортировки простым выбором. Число сравнений ключей не зависит от начального порядка ключей. Опе­ рация сравнения выполняется в теле цикла с управляющей перемен­ ной к и средним числом повторений size/2. Этот цикл, в свою оче­ редь, находится в теле цикла с управляющей переменной L и числом повторений size-\. Таким образом, число сравнений

С = {size -1) • size 12

Число пересылок, напротив, зависит от начального порядка ключей. Если принять, что операция сравнения в теле цикла по к да­ ет результат "истина" в половине случаев, то среднее число пересы­ лок в этом цикле равно size!А. Цикл по L, как указывалось выше, вы­ полняется sizeA раз и в теле цикла выполняется три пересылки и цикл по к. С учетом этого число пересылок

М = (3 + size 14) • {size -1)

Получаем, что при сортировке простым выбором и число сравнений, и число пересылок пропорционально size'^.

15.3. Сортировка массива простыми включениями

Идея алгоритма пояснена на рис. 61, а пример сортировки мас­ сива данным методом иллюстрирует рис. 64. Алгоритм сортировки простыми включениями выглядит следующим образом:

for (	2=2/	JL <	sizel/	l+-h	)
{		= arr	[ i	];
copy						место	среди	отсортированных
//	Вставка		copy	на нужное
//		элементов		массива	агг[	О ],	. . . ,	arrf i-l ]

}

При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы "просеивать" сору, сравнивая его с очеред­ ным элементом arr[J ] и, либо вставляя сору, либо пересылая arr[j ] направо и передвигаясь налево. Заметим, что "просеивание" может закончиться при двух различных условиях.

1. Найден элемент arr[j ] с ключом, меньшим, чем у сору.

2. Достигнут левый конец упорядоченного сегмента и, следо­ вательно, сору нужно вставить в левый конец упорядоченного сег­ мента.

248

	44 1	55		12	42	94	18	06	67	i = 2
ключей элементов		^ 1			42	94	18	06	67	1 = 3
массива	44	55	1	12
	12	44		1		94	18	06	67	i = 4
				55 1 42
	12	^		44	1		18	06	67	1 = 5
		42			55 1 94
	12	42		44	55	94 1 18		06	67	1 = 6
	12	18		42	44	55	941	06	67	i = 7
	06	12		18	42	44	55	941	67	i = 8
Массив отсортирован 06		12		18	42	44	55	67	94

Рис. 64. Пример сортировки массива простыми включениями

Это типичный пример цикла с двумя условиями окончания. При записи подобных циклов можно использовать известный прием фиктивного элемента ("барьера"), установив "барьер" слева в упоря­ доченной части массива агг[ О ] = сору (рис. 65).

0	1	2		...	sJze-1
I	г	1 1	~		"Г
агг
«Барьер»				Сортируемый массив

Рис. 65. Использование "барьера" при сортировке массива ростыми включениями

Прототип функции сортировки массива простыми включения­ ми, ее определение и пример вызова даны в примере, приведенном в подразд. 15.2. Теперь наступила пора познакомиться с ними.

Обратите внимание на то, что при использовании метода "ле­ вого барьера" размер массива, подлежащего сортировке, увеличен на один элемент. При этом элемент массива с нулевым индексом яв­ ляется вспомогательным и не сортируется. Таким образом, в масси­ ве сортируются элементы с индексами 1, 2, ..., size 1-1. По этой при­ чине для сортировки простым выбором используются функции раз­ мещения сортируемого массива в динамической памяти, заполнения его значениями из файла и печати значений элементов массива в файл, отличающиеся от аналогичных функций для других методов.

Эффективность сортировки. Число С,, сравнений ключей

249