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]

Дата

Подп.


 

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

78989. Научное сообщество, его типология и историческая эволюция. Научная школа как информациогенная среда. Особенности научного сообщества в постиндустриальную эпоху 49.5 KB
  Исторические типы научных сообществ: Философские школы школа Эпикура Сад школа Аристотеля Лицей школа Платона Академия Стоики Александрийская школа сосредоточены все виды наук; богословские школы монастырские школы; республика ученых начало XVII века научные сообщества эпохи дисциплинарно организационной науки XVIII XIX в.; междисциплинарные сообщества деятелей науки XX век; научные школы сообщества единомышленников в решении одних и тех же проблем; научные направления; научные коллективы...
78990. Культурологический дискурс науки. Гуманитарные аспекты развития научного знания. Научная рациональность и проблема диалога культур 39 KB
  Научная рациональность и проблема диалога культур Наука является одной из определяющих особенностей современной культуры и возможно самым динамичным ее компонентом. Научная рациональность один из типов рациональности как таковой. Рациональность от лат. Научная рациональность абсолютизирует роль логикометодологических процедур в познании отделяет познавательные акты от ценностных ориентаций сознания и в целом любых проявлений человеческой неразумности иррациональности.
78991. Этические аспекты научной деятельности. Понятие научного этоса и проблема его современного расширения 28.5 KB
  Этика науки изучает нравственные основы научной деятельности совокупность ценностных принципов принятых в научном сообществе и концентрирует в себе социальный и гуманистический аспекты науки. Этические проблемы современной науки являются чрезвычайно актуальными и значимыми. На страже этических принципов стоит институт ссылок как академическая составляющая науки. Этос науки правило деятельности ученого отвечает следующим требованиям: 1 универсализм неличностный характер научного знания его объективность деятельность в области...
78992. Аксиологические проблемы научной деятельности. Научные ценности в их соотношении с социальными. Проблема идеологизированной науки 35.5 KB
  Проблема идеологизированной науки. Оно должно исключать ценностные аспекты характерно для классической и неклассической науки. Весь XX век в философии науки шла дискуссия о роли ценностей в науке: являются ли они необходимой движущей силой для развития науки или условием успешной деятельности ученых служит их освобождение от всех возможных ценностных ориентиров Возможно ли полностью исключить из суждений о фактах ценностные предпочтения и познать объект как таковой сам по себе Необходимо ли и возможно ли противопоставление фактичности...
78993. Эстетические аспекты научной деятельности, их функция и роль в формировании идеала науки. Наука и искусство в их соотношении 19.76 KB
  Наука и искусство в их соотношении. В современной философской литературе понятия эстетики отнесены главным образом к искусству эстетическое содержание научного творчества и других видов человеческой деятельности не связанных с искусством практически не рассматривается. В 1931 голу была опубликована книга моего отца драматурга и искусствоведа В. Наука сближается с искусством то есть с эстетикой и высшее эстетическое значение имеет простая и ясная картина мира.
78994. Космологический дискурс научного знания. Наука как часть ноосферы. Проблемы современной экологической этики 23.12 KB
  Понятие экологической этики Подъем этики окружающей среды был в первый День Земли в 1970 году когда сторонники защиты окружающей среды вынудили философов которые работали в области окружающей среды сгруппироваться чтобы сделать некоторые замечания об этике окружающей среды. Дискуссия началась в 1974 когда австралиец именуемый John Pssmore опубликовал книгу пол названием Ответственность человека за природу: экологические проблемы и западные традиции в которой он аргументировал точку зрения что сохранение окружающей среды и ее...
78995. Наука в контексте традиционалистского и техногенного цивилизационного развития. Футурологические аспекты научного знания 16.91 KB
  Понятие цивилизации впервые возникло в 18 веке во Франции для обозначения общества в котором господствует свобода равенство и братство. Традиционные цивилизации. Техногенные цивилизации. Особенности техногенной цивилизации: Ориентация на совершенствование техники производства.
78996. Научное знание в контексте глобальных проблем. Особенности развития науки в глобализующемся мире. Роль науки в преодолении современного кризиса 14.1 KB
  К глобальным проблемам современности относят экологические демографические проблемы войны и мира проблемы кризиса культуры проблемы терроризма. Это включает в себя медикобиологические проблемы указывающие риски для здоровья современного человека сокращение ареалов нищеты и бедности комплекс минеральносырьевых проблем проблемы энергетического кризиса проблемы прекращения гонки вооружения и предотвращения использования средств массового уничтожения. Глобальные экологические проблемы требуют от ученых и предпринимателей повышения...
78997. Философские проблемы науки, их сущность, специфика и типология. Историко-философские, онтологические, логико-методологические, аксиологические аспекты науки в их соотношении 18.15 KB
  Философские проблемы науки их сущность специфика и типология. Историкофилософские онтологические логикометодологические аксиологические аспекты науки в их соотношении. Предметом философии науки являются общие закономерности и тенденции научного познания как особой деятельности по производству научных знаний взятых в их историческом развитии и рассматриваемых в исторически изменяющемся социокультурном контексте. Философия науки иногда отождествляется с ближними областями науковедения наукометрии социологии науки что неправомерно.