Лабораторная работа №1 Вариант 8

2

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

Лабораторная работа №1

по дисциплине

«Технология программирования»

на тему:

«Программирование алгоритмов сортировки»

Студент

Ельшаева Н.А.

^подпись, дата

^фамилия, инициалы

Группа

АС-09

Принял

Домашнев П.А.

^ученая степень, звание

^подпись, дата

^фамилия, инициалы

Липецк 2010

1. Задание

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

Вариант	ключ	Запись 0 – только ключ, 1 – ключ и другие данные различных типов	Метод внутренней сортировки
8	int[]	0	1

Метод выбора (1)

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

2. Блок-схема

j>0

j<3

q>0

q<3

\

p>q*3

p>q*3+3

l>0

l<3

i>p

i<q*3+3

j<3

j>0

да

нет

да

нет

l>0

l<3

j>0

j<3

i>0

i<3

q>0

q<9

l<3

p>0

p<3

l>0

j>0

j<3

да

нет

l>0

l<3

да

нет

i>0

i<9

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

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <locale.h>

void main()

{

setlocale(LC_ALL,"Rus");

const int N=9, n=3, k=3;/*N -количество строк, n -количество элементов в ключе, k -количество лент*/

int L[N][n],L_new[N][n],i,j,q,p,h,l,dop,min[n],key,sch[k];/*L[N][n] - исходная лента

L_new[N][n] - получаемая лента

i,j,q,p,l - счетчики

h,dop,key вспомогательные переменные

min[n] - вспомогательный массив для поиска минимального элемента

sch[k]- счетчики лент*/

for(i=0;i<N;i++)//ввод ленты

{

printf("\nВведите ленту №%d:\n",i);

for(j=0;j<n;j++)

{

printf("Введите элемент %d: ", j);

scanf("%d",&L[i][j]);

}

}

/*сортировка каждой из лент методом выбора*/

for(q=0;q<k;q++)//счетчик по количеству лент

for(p=q*N/k;p<(q*N/k+N/k);p++)//счетчик элементов нужной ленты

{

for(l=0;l<n;l++)//инициализация массива мин для сравнения

min[l]=777;

for(i=p;i<(q*N/k+N/k);i++)//сортировка методом выбора

{

key=0;

for(j=0;j<n;j++)//нахождение минимального ключа

{

if((key!=1)&&(L[i][j]<min[j]))

{

for(l=0;l<n;l++)

min[l]=L[i][l];

h=i;//запоминание номера минимальной ленты

key=1;

}

else if((key!=1)&&(L[i][j]==min[j]))

key=0;

else

key=1;

}

}

for(j=0;j<n;j++)//обмен элементов в ленте

{

dop=L[h][j];

L[h][j]=L[p][j];

L[p][j]=dop;

}

}

for(i=0;i<k;i++)//инициализация счетчиков лент

sch[i]=i*N/k;

for(q=0;q<N;q++)//счетчик по количеству элементов

{

for(l=0;l<n;l++)//инициализация массива мин для сравнения

min[l]=777;

for(p=0;p<k;p++)//счетчик по количеству лент

{

key=0;

for(j=0;j<n;j++)//слияние лент

{

if((sch[p]<((p+1)*N/k))&&(key!=1)&&(L[sch[p]][j]<min[j]))

{

for(l=0;l<n;l++)

min[l]=L[sch[p]][l];

h=p;

key=1;

}

else if((sch[p]<((p+1)*N/k))&&(key!=1)&&(L[sch[p]][j]==min[j]))

key=0;

else

key=1;

}

}

for(j=0;j<n;j++)//запись нужной строки в нужный массив

L_new[q][j]=L[sch[h]][j];

sch[h]++;

}

for(i=0;i<N;i++)//вывод получившегося массива

{

for(j=0;j<n;j++)

printf("%d ", L_new[i][j]);

printf("\n");

}

getch();

}

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

Выводы о проделанной работе

При выполнении данной лабораторной работы я получила навыки программирования методов сортировки.

Список использованной литературы

1. Шилдт Г. Искусство программирования на C++. БХВ.2005

2. Шилдт Г. C++ Руководство для начинающих. Вильямс.2005

3. Страуструп Б. Язык программирования С++. Специальное издание, 3-изд. Бином.2004