43434

Исследование методов сортировки расстановкой и с поиском минимума

Курсовая

Информатика, кибернетика и программирование

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

Русский

2013-11-05

338.5 KB

4 чел.

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

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

Факультет автоматизации и информационных технологий

Кафедра информационных технологий

СОРТИРОВКА МАСИВОВ

Пояснительная записка

(ИТ - 220301.013 ПЗ)


Руководитель:  

___________  Кузьмин Д.Н.
(подпись)
_________________2008г
(оценка, дата)

Разработал:
студент группы 22-1
___________  Зубов А.В.
(подпись)
_________________2008г

(дата)

Красноярск, 2008


Задание на курсовую работу

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

Метод сортировки:

  1.  Расстановкой.
  2.  С поиском минимума.


Реферат

Целью данной курсовой работы является исследование методов сортировки расстановкой и с поиском минимума. Сравнить их эффективность между собой. Сделать выводы.

Курсовая работа содержит 2 программы на языке C/C++ и пояснительную записку из 16 страниц текста, 2 графиков, 4 рисунков.


Содержание

[0.1] Реферат

[0.2]
Содержание

[1]
Введение

[2]
Сортировка расстановкой

[3] Сортировка с поиском минимума

[4] Заключение

[5]
Библиографический список

[6]
Приложение


Введение

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

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


Сортировка расстановкой

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

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

#include<stdio.h>

#include<conio.h>

#include<time.h>

#include<stdlib.h>

typedef int array_type;

#define HB 1000

long locate(int *a,long n)

{

    long i,j,                           // счетчики для цикла 

        c,c2,                            // переменные для промежуточного хранения

        k=0;                            // количество операций сравнения

     for(i=0;i<n-1;i++)

  {

         c2=i;

           for(j=i+1;j<n;j++)

         {

                k++;

                if (a[c2]>a[j]) c2=j;

          }

          c=a[i];

          a[i]=a[c2];

          a[c2]=c;

   }

 return k;

}

void main()

{struct  time tstart,tend;          // Объявление процедуры подсчета времени

int mas[HB];                                                     

int i;

clrscr();

randomize();

for (i=0;i<HB;i++)

 {

 mas[i]=random(20);          // Задание массива случайными числами

 }

gettime(&tstart);

gettime(&tend);

if (tstart.ti_hund>tend.ti_hund)

{

tend.ti_hund=tend.ti_hund+100;

tend.ti_sec=tend.ti_sec-1;

}

tstart.ti_hund=tend.ti_hund-tstart.ti_hund;

if (tstart.ti_sec>tend.ti_sec)

{

tend.ti_sec=tend.ti_sec+100;

tend.ti_min=tend.ti_min-1;

}

tstart.ti_sec=tend.ti_sec-tstart.ti_sec;

tstart.ti_min=tend.ti_min-tstart.ti_min;

printf("%02d:%02d.%02d\n",tstart.ti_min,tstart.ti_sec,tstart.ti_hund);

printf("sravneniya %ld\n",kol);   // Вывод на экран количества сравнений,

printf("perestanovki %ld",k);      // времени и количества перестановок

getch();

}

В программе используются переменные:

mas[HB] – сортируемый массив произвольных целых чисел типа int.

k – количество перестановок, тип long.

i – счетчик элементов массива, тип int.

tmp – промежуточная переменная для записи элементов массива, тип int.

Сортировка с поиском минимума

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

Исходный массив А длинной N разбивается на две части: итог и остаток. Участок массива, называется итогом, располагается с начала массива и должен быть упорядоченным, а участок массива, называемый остатком, располагается вплотную за итогом и содержит числа не сортированной части исходного массива. i—последний элемент итога.

#include <conio.h>

#include <dos.h>

#include <stdio.h>

#include <stdlib.h>

long sortmin(int *a,long n)

{

long i,j,k=0,min;

int tmp;

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

{

min=j;

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

 {

 k++;

 if (a[i]<a[min]) min=i;

 }

tmp=a[j];

a[j]=a[min];

a[min]=tmp;

}

return k;

}

void textline(int n)

{

int i;

for(i=0;i<n;i++) cprintf("Ы");

printf("\n");

}

main()

{

int a[15000],b[15000];

long i,n,k1,time1,time2;

struct time t;

textmode(64);

textcolor(15);

textbackground(0);

clrscr();

randomize();

n=15;

textcolor(11);

cprintf("Исходный массив:\n\r");

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

{

a[i]=random(199)-99;

cprintf("%4d",a[i]);

}

sortmin(a,n);

textcolor(14);

cprintf("\n\n\rОтсортированный массив:\n\r");

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

cprintf("%4d",a[i]);

textcolor(10);

cprintf("\n\n\rНажмите “пробел” для продолжения.");

while (getch()!=32);

textcolor(15);

clrscr();

textcolor(13);

cprintf("Количество элементов массива \n\r");

textcolor(10);

cprintf("Количество операций сравнения в методе сортировки с поиском минимума \n\r");

textcolor(14);

cprintf("Время работы сортировки с поиском минимума\n\r");

printf("\n");

for(n=1500;n<12001;n+=1500)

{

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

 {

 a[i]=random(199)-99;

 b[i]=a[i];

 }

gettime(&t);

time1=t.ti_hour*100*60*60+t.ti_min*100*60+t.ti_sec*100+t.ti_hund;

k1=sortmin(a,n);

gettime(&t);

time2=t.ti_hour*100*60*60+t.ti_min*100*60+t.ti_sec*100+t.ti_hund;

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

 a[i]=b[i];

textcolor(13);

cprintf("%10ld ",n);

textline(n/200);

textcolor(10);

cprintf("%10ld ",k1);

textline(k1/1100000);

textcolor(14);

cprintf("%10.2f ",(time2-time1)/100.0);

textline((time2-time1)/2);

}

textcolor(9);

cprintf("\n\          Нажмите любую клавишу для выхода из программы");

getch();

}

Пример выполнения программы можно привести на сортировки массива из 3000 элементов заданных случайными числами.

Время сортировки 0.06 секунды.

Количество сравнений 4501499.

  

 

Заключение

Данные курсовой работы позволяют сравнить между собой сортировку расстановкой и сортировку с поиском минимума.

Сортировка расстановкой более проста в написании, чем сортировка с поиском минимума по времени сортировки, особенно это различие, заметно при сортировки массивов с количеством элементов более 3000. А вот по количеству операций сравнения эти два метода идут практически вместе на незначительном отличии, разница начинает чувствоваться только при количестве элементов в массиве более 4500, метод с поиском минимума проводит немного больше операций сравнения.


Библиографический список

  1.  Культин Н. C/C++ в задачах и примерах [Текст] / Н. Культин. – СПб.: БХВ-Петербург, 2005.-288с.
  2.  Баринова Т.Н., Зубарева Н.М., Трапезников С.В. Информатика: Часть 1. Создание текстовых документов. Обработка данных средствами электронных таблиц [Текст] / Т.Н. Баринова, Н.М. Зубарева, С.В. Трапезников. – Красноярск: СибГТУ, 2003.-90 с.
  3.  Иванилова Т.Н. Информатика. Операционные системы и оболочки. [Текст] / Т.Н. Иванилова. – Красноярск: СибГТУ, 2003.-66 с.


Приложение

Диаграмма 2. Зависимость операций сравнения от количества элементов массива. Сплошной линией показан метод вставки, прерывистой метод расстановкой. Количество операций сравнения в тысячах на оси ординат, количество элементов массива на оси абсцисс.

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

Рисунок 1. Блок-схема процедуры сортировки вставкой.

Рисунок 2. Блок-схема процедуры сортировки вставкой.


Рисунок 2.Блок-схема процедуры сортировки с поиском минимума.

ИТ.220301.013.ПЗ

Н.конт.

Пров.

Разраб.

Кузьмин Д.Н.

Зубов А.В.

№ докум.

Подп.

Дата

Лит.

3

Лист

16

Листов

СибГТУ гр.22-1

Изм.

Лист

Пояснительная записка

ИТ.220301.013.ПЗ

№ докум.

Подп.

Дата

4

Лист

Изм.

Лист

Лист

Изм.

Лист

9

ата

Подп.

№ докум.

ИТ.220301.013.ПЗ

ИТ.220301.042.ПЗ

ИТ.220301.013.ПЗ

№ докум.

Подп.

Дата

5

Лист

Изм.

Лист

ИТ.220301.013.ПЗ

№ докум.

Подп.

Дата

10

Лист

Изм.

Лист

    A[I]=A[C2]

       A[C2]=C

          I=I+1

+

-

-

-

+

+

        K=K+1

            J<N

C2=I,   J=I+1

           I<N

    K=0,    I=0

   A[C2]>A[J]

          J=J+1

ИТ.220301.013.ПЗ

№ докум.

Подп.

Дата

11

Лист

Изм.

Лист

Лист

Изм.

Лист

6

Лист

Изм.

Лист

7

Дата

Подп.

№ докум.

Лист

Изм.

Лист

8

Дата

Подп.

№ докум.

ИТ.220301.013.ПЗ

ИТ.654700.013.ПЗ

ИТ.220301.013.ПЗ

ИТ.220301.013.ПЗ

№ докум.

          C2=J

начало

конец

       C=A[I]

Дата

Подп.


 

А также другие работы, которые могут Вас заинтересовать

35130. Расчёт пространственного одноэтажного промышленного здания, оборудованного мостовым краном 414.33 KB
  Список литературы Исходные данные Количество пролетов – 3; Длина пролета – l1 = 18 м; Длина здания – l = 168 м; Несущая конструкция покрытия – балка; Шаг колонн – 6 м; Высота до верха рельса – 84 м; Грузоподъемность крана – 15 т; Расчетное сопротивление грунта – Rгр =019 МПа; Место строительства – г. Расчет крайней колонны Данные для расчета сечений: бетон тяжелый класса B15 подвергнутый тепловой обработке при атмосферном давлении Rb = 85 МПа; Rbt = 075 МПа; Eb = 20500 МПа. Арматура класса АIII d 10 мм RS = RSC =...
35131. Форматирование результатов запроса 82 KB
  Например можно применить следующую команду чтобы увидеть определенные поля таблицы Slespeople упорядоченные по убыванию поля commission comm: SELECT snme comm FROM Slespeople ORDER BY 2 DESC; Мы рассматриваем это свойство ORDER BY для того чтобы продемонстрировать возможность его использования со столбцами выходных данных; эта процедура аналогична применению ORDER BY со столбцами таблицы. Например чтобы подсчитать заявки orders для каждого продавца slespeople и вывести результаты в убывающем порядке: SELECT snum COUNT DISTINCT...
35132. Создание таблиц 90 KB
  Команда CRETE TBLE Таблицы определяются с помощью команды CRETE TBLE создающей пустую таблицу таблицу не имеющую строк. Команда CRETE TBLE определяет имя таблицы и множество поименованных столбцов в указанном порядке. Синтаксис команды CRETE TBLE: CRETE TBLE имя таблицы имя столбца тип данных [ размер ] имя столбца тип данных [ размер ]. Поскольку пробелы используются для разделения отдельных частей команд в SQL их нельзя использовать как часть имени таблицы.
35133. Основные понятия SQL 152.5 KB
  Он используется для связи с такими системами управления базами данных как Orcle INGRES Informix Sybse SQLbse Microsoft SQL Server DB2 СУБД самой IBM продуктами SQL DC Prdox ccess pproch и многими другими. Обычно продукт базы данных включает не только СУБД. Собственно СУБД иногда ее называют исполнительной системой или исполнительным механизмом базы данных является рабочей лошадкой продукта. Она хранит данные осуществляет поиск и выборку данных а также записывает данные посредством исполнения операторов SQL В вычислительной...
35134. Альтернативная программная реализация выборки и модификации данных в базе данных Interbase 34.5 KB
  Конфигурируется ODBCисточник реализующий доступ к БД Interbse. В DBE dministrtor настраивается псевдоним БД доступной через BDE и представляющей собой в данном случае ODBCисточник. В отличие от 3го способа являющегося усовершенствованным подходом BDE 1й способ является более универсальным и более ресурсоемким в первую очередь по критерию времени поскольку представляет собой использование промежуточного уровня BDE и промежуточного уровня ODBC а 2й – менее универсальным и менее ресурсоемким поскольку предполагает использование...
35135. Пример реализации трехзвенной архитектуры 39.5 KB
  Два разрабатываемых при этом программных компонента – это сервер приложений и клиент взаимодействующие по протоколу DCOM. Разработка сервера приложений Основные шаги создания сервера приложений: Создание удаленного модуля данных Remote Dt Module. Однократный запуск программы с целью регистрации сервера приложений в реестре Windows. Для распределенного использования разработанных клиентского и серверного приложений требуется установка некоторых дополнительных программных компонент.
35136. Пример реализации обмена данными с Microsoft Excel 45.5 KB
  Создание новой книги Vrint MSBooks; MSBooks = MSExcel. Создание нового листа книги. Сохранение книги. Создание нового листа книги.
35137. Изучение формата баз данных Visual FoxPro 549.5 KB
  После заголовка таблицы следует цепочка 32байтовых описаний полей таблица 4.fmp Fp 01 1 YY Год последнего обновления таблицы Все 02 1 MM Месяц последнего обновления таблицы Все 03 1 DD День последнего обновления таблицы Все 04 4 RecordsCount Количество записей в таблице Все 08 2 HederSize Размер заголовка в байтах Все 10 2 RecordSize Размер записи в байтах Все 12 2 0x000x00 Зарезервировано Все 14 1 0x01 Начало транзакции D4 D5 0x00 Конец транзакции D4 D5 0x00 Игнорируется FS D3 Fb Fp CL 15 1 0x01 Закодировано D4 D5 0x00 Нормальная...
35138. Разработка файл-серверной информационной системы с использованием технологий Borland 47.5 KB
  Программное использование БД Простейший случай Для обращения к таблицам используются невизуальные компоненты TTble и TDtSource закладки Dt ccess и BDE палитры компонентов и ряд визуальных: TDBGrid TDBEdit TDBLookupComboBox и т. В компоненте TTble устанавливаются свойства TbleNme TbleType. В последнем случае псевдоним БД указывается в свойстве DtbseNme объекта TTble. В компоненте TDtSource устанавливается свойство DtSet как указатель на TTble.