Титульный лист. Задание кафедры, соответствующее варианту. Задание кафедры, соответствующее варианту

Задание кафедры, соответствующее варианту.

12. Цель работы.

Краткие теоретические сведения.

Формализованный алгоритм.

Листинг программы.

16. Контрольный пример.

17. Выводы по работе.

Задание

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

Таблица 5

Варианты заданий

№ п/п	Ключ	Запись	Метод внутренней сортировки
	int	ключ, char[], float	Метод обмена
	int[]	только ключ	Сортировка с помощью дерева
	float	ключ, float[], char[]	Сортировка включением
	float[]	только ключ	Сортировка разделением
	char	ключ, int[], char	Сортировка разделением
	char[]	только ключ	Метод обмена
	int	ключ, char, float	Сортировка с помощью дерева
	int[]	только ключ	Метод выбора
	float	ключ, int[], char	Метод выбора
	float[]	только ключ	Сортировка включением
	char	только ключ	Сортировка включением
	char[]	только ключ	Метод выбора
	int	ключ, char[]	Сортировка включением
	int[]	только ключ	Метод обмена
	float	ключ, char[], int	Сортировка разделением
	float[]	только ключ	Метод обмена
	char	ключ, char[], int	Сортировка с помощью дерева
	char[]	только ключ	Сортировка включением

 

Пример выполнения работы

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

Ключ – int

Запись – только ключ

Метод внутренней сортировки – Метод Шелла

 

Блок – схема программы представлена на рис. 9.

Листинг программы

#include< stdio.h>

#include< windows.h>

#include< conio.h>

#include< math.h>

#include< string.h>

 

void shell(int *items, int count)

{

register int i, j, x, gap;

gap=(int)(count/2);

while(gap> 0)

 

Рис. 9. Блок-схема программы

 

{

for(i=gap; i< count; i++)

{

x=items[i];

for(j=i-gap; (x < items[j]) & & (j > = 0); j=j-gap)

{

items[j+gap] = items[j];

}

items[j+gap] = x;

}

gap=(int)(gap/2);

}

}

 

void main()

{

SYSTEMTIME tim;

GetSystemTime(& tim);

srand(tim.wMilliseconds);

int count, k=0, *source, **a, *b, *stek;

printf(" Puts count elements: \t");

scanf(" %d", & count);

 

int N=(int)ceil(sqrt((float)count));

source=(int*)malloc(sizeof(int)*count);

a=(int**)malloc(sizeof(int*)*N);

b=(int*)malloc(sizeof(int)*N);

stek=(int*)malloc(sizeof(int)*N);

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

{

a[i]=(int*)malloc(sizeof(int));

b[i]=0;

}

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

{

k=i%N;

source[i]=rand();

a[k]=(int*)realloc(a[k], sizeof(int)*(++b[k]));

a[k][b[k]-1]=source[i];

printf(" %d ", source[i]);

}

printf(" \n\n");

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

{

shell(a[i], b[i]);

for(int j=0; j< b[i]; j++)printf(" %d\t", a[i][j]);

printf(" \n");

}

printf(" \n");

for(int i=count-1; i> -1; i--)

{

k=0;

if(b[0]> 0)stek[0]=a[0][b[0]-1];

else

{

int j=0;

while((b[j]< =0)& & (j< N))j++;

j--;

stek[0]=a[j][b[j]-1];

b[0]=b[j];

b[j]=0;

}

for(int j=1; j< N; j++)

{

if(b[j]< =0)continue;

stek[j]=a[j][b[j]-1];

if(stek[j]> stek[0])

{

stek[0]=stek[j];

k=j;

}

}

source[i]=stek[0];

b[k]--;

}

for(int i=0; i< count; i++)printf(" %d ", source[i]);

free(source);

getch();

}