43255

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

Курсовая

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

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

Русский

2013-11-04

211 KB

6 чел.

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

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

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

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

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

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

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

(ИТ - 220301.015 ПЗ)


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

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

Разработал:
студент группы 22-1
Колотов  А.С.

__________  
(подпись)
_________________2008г

(дата)

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


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

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

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

  1.  С поиском минимума.
  2.  Деревом.


Реферат

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

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


Содержание

[0.1] Реферат

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

[1]
Введение

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

[3] Сортировка «методом дерева»

[4] Основная часть программы

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

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

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


Введение

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

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


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

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

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

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;

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

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

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


Сортировка «методом дерева»

Двоичным деревом назовем упорядоченную структуру данных, в которой каждому элементу -- предшественнику или корню (под)дерева -- поставлены в соответствие по крайней мере два других элемента (преемника). Причем для каждого предшественника выполнено следующее правило: левый преемник всегда меньше, а правый преемник всегда больше или равен предшественнику. Если мы составим такое дерево из букв слова "СОРТИР", сравнивая ASCII коды букв, то получим следующую структуру:

                                  С

                                /   \

                               О     Т

                             /   \

                            И     Р

Как видно, узел "С" имеет два преемника: левый "О" и правый "Т". Если составить бинарное дерево из элементов неупорядоченного массива, то в общем случае дерево получится достаточно хорошо заполненным (а если массив уже был рассортирован, то дерево выродится в линейный список). Если мы будем обходить дерево по правилу "ЛЕВЫЙ преемник - КОРЕНЬ - ПРАВЫЙ преемник", то, записывая все встречающиеся элементы в массив, мы получим упорядоченное в порядке возрастания множество. На этом и основана идея сортировки деревом.

Использование такой сортировки удобно тогда, когда удобно представлять данные в виде дерева.

Недостаток метода - требуется много памяти. В приведеном примере - дополнительный мегабайт данных на каждые 256k элементов.

long treesort(int *a, long n)

{

long i,j,k=0,l,r,x,z;

l=n/2+1;

r=n;

while (l>1)

 {

  l--;

  i=l;

  j=2*l;

  x=a[l-1];

  k++;

  if ((j<r)&&(a[j-1]<a[j]))

  j++;

  while ((j<=r)&&(x<a[j-1]))

   {

    x=a[i-1];

  a[i-1]=a[j-1];

    a[j-1]=x;

    i=j;

    j=2*j;

    k++;

    if ((j<r)&&(a[j-1]<a[j]))

   j++;

   }

 }

while (r>1)

 {

  x=a[0];

  a[0]=a[r-1];

  a[r-1]=x;

  r--;

  i=l;

  j=2*l;

  x=a[l-1];

  k++;

  if ((j<r)&&(a[j-1]<a[j]))

  j++;

  while ((j<=r)&&(x<a[j-1]))

   {

    x=a[i-1];

    a[i-1]=a[j-1];

    a[j-1]=x;

    i=j;

    j=2*j;

    k++;

    if ((j<r)&&(a[j-1]<a[j]))

   j++;

   }

 }

return k;

}

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

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

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

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

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

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

Основная часть программы

#include <conio.h>

#include <dos.h>

#include <stdio.h>

#include <stdlib.h>

main()

{

int a[15000],b[15000];

long i,n,k1,k2,time1,time2,time3,time4;

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");

textcolor(11);

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

textcolor(15);

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];

  gettime(&t);

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

  k2=treesort(a,n);

  gettime(&t);

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

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(11);

cprintf("%10ld ",k2);

textline(k2/1100000);

textcolor(15);

cprintf("%10.2f ",(time4-time3)/100.0);

textline((time4-time3)/2);

 }

textcolor(9);

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

getch();

}

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

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

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

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

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

time1,time2,time3,time4 – переменные для определение времени работы функций сортировки, тип long.

Заключение

В данном примере метод сортировки с поиском минимума оказался  менее эффективным, чем сортировка методом дерева, как по времени, так и по количеству операций сравнения. Из примера видно, что количество операций сравнения отличаются в сотни раз. Именно этим и объясняется эффективность сортировки методом дерева.


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

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

3.     Иванилова Т.Н. Информатика. Операционные системы и оболочки.   [Текст] / Т.Н. Иванилова. – Красноярск: СибГТУ, 2003.-66 с.


Приложение

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

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


Рисунок 1. Блок схема сортировки с поиском минимума.

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

Рисунок 3. Блок схема алгоритма основной программы.

ИТ.220301.015.ПЗ

Н.конт.

Пров.

Разраб.

Кузьмин Д.Н.

Колотов А.С.

№ докум.

Подп.

Дата

Лит.

3

Лист

17

Листов

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

Изм.

Лист

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

ИТ.220301.015.ПЗ

докум.

Подп.

Дата

4

Лист

Изм.

Лист

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

5

Лист

Изм.

Лист

Лист

Изм.

Лист

6

Дата

Подп.

№ докум.

ИТ.654700.138.ПЗ

Лист

Изм.

Лист

8

Дата

Подп.

№ докум.

ИТ.220301.015.ПЗ

Лист

Изм.

Лист

7

Дата

Подп.

№ докум.

ИТ.220301.015.ПЗ

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

9

Лист

Изм.

Лист

Лист

Изм.

Лист

10

Дата

Подп.

№ докум.

ИТ.220301.015.ПЗ

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

11

Лист

Изм.

Лист

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

12

Лист

Изм.

Лист

Лист

Изм.

Лист

14

Дата

Подп.

№ докум.

ИТ.220301.015.ПЗ

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

13

Лист

Изм.

Лист

ИТ.220301.015.ПЗ

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

15

Лист

Изм.

Лист

№ докум.

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

16

Лист

Изм.

Лист

Подп.

Дата

17

Лист

Изм.

Лист

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

4

Лист

Изм.

Лист

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

18

Лист

Изм.

Лист

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

4

Лист

Изм.

Лист

ИТ.220301.015.ПЗ

№ докум.

Подп.

Дата

19

Лист

Изм.

Лист


 

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

43601. МЕРOПРИЯТИЯ ПO УЛУЧШЕНИЮ ЭФФЕКТИВНOСТИ УПРAВЛЕНИЯ КAПИТАЛОМ НА ИП ЗИНИНA А.И 233.92 KB
  3 Кoнцепции упрвления кпиталом нализ сoстава и структуры кпитала предприятия. Пoлучение прибыли на сегoдня этo результт првильных решений o прoпорциях влoжения кпитала принятых дo нчала oперационной деятельнoсти предприятия. Oт тoго как испoльзуется кпитал звисит величин прибыли предприятия следовательнo и егo дльнейшее рзвитие. В связи с этим oсобое знчение приoбретает исследoвание прoблем связнных с пoвышением эффективнoсти использoвания кпитала предприятия тк кк движение стoимости ресурсoв и их кругooборот станoвятся...
43602. Управление техническим состоянием осуществляется на основе научно обосновательной системой технического обслуживания и ремонта СПК «Петровщина» 208.78 KB
  СПК «Петровщина» был организован в 40-х годах в западной части Глубокского района Витебской области. Сельскохозяйственный производственный кооператив был создан путем реорганизации колхоза «Победа» на основании решения Глубокского райисполкома.
43603. ФОРМУВАННЯ РЕКЛАМНОЇ КАМПАНІЇ ТУРИСТИЧНОЇ АГЕНЦІЇ 49.16 KB
  Розрахунки необхідного бюджету для проведення рекламної кампанії ВИСНОВКИ ПЕРЕЛІК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ ДОДАТКИ РОЗДІЛ 1 СУЧАСНІ ТЕОРЕТИЧНІ ТА МЕТОДИЧНІ СКЛАДОВІ РЕКЛАМНОЇ КАМПАНІЇ В ТУРИСТИЧНОМУ БІЗНЕСІ Нині одним з найпоширеніших засобів стимулювання попиту на різні види продукції і послуги є реклама. Проте для багатьох організацій чисто інформативна реклама має другорядне значення. На стадії спаду реклама в основному недоцільна виключаючи необхідність інформування про розпродажі товарів. Спочатку реклама потрібна для того щоб створити...
43604. Дослідження історії і методологічних основ формування поглядів на простір і час 338.51 KB
  Дослідження методологічних підходів до формування понять матерії, простору і часу в історичному їх розвитку є цікавим і науково важливим, оскільки вся фізична наука будувалася і будується в наш час з урахуванням сформованих на кожному історичному періоді поглядів на ці філософські категорії.
43605. Приготовление блюда «Судак фри с картофелем, соус томатный» 524.83 KB
  Первые столовые возникли на Путиловском заводе в Петрограде, а за тем в Москве и других городах. В условиях острой нехватки продуктов и хозяйственной разрухи в период гражданской войны и иностранной интервенции общественные столовые сыграли большую роль в обеспечении питанием населения.
43606. Особенности регистрации прав отдельных категорий недвижимого имущества и сделок с ними 303.56 KB
  Рынок недвижимости в России пережил период становления и в настоящее время существует необходимость осмыслить всё к чему пришла правовая мысль в области оборота недвижимого имущества. Учитывая большое значение объектов недвижимости в жизни и деятельности граждан и юридических лиц а также в гражданском обороте закон закрепил её специальный правовой режим. Актуальность темы выпускной квалификационной работы состоит в том что в настоящее время институт недвижимости занимает одно из основных мест в современном обществе. Целью выпускной...
43607. Практические применения методов оценки доходной недвижимости 199.32 KB
  Недвижимость выступает основой личного существования для граждан и служит базой для хозяйственной деятельности и развития предприятий и организаций всех форм собственности. В России происходит активное формирование и развитие рынка недвижимости и все большее число граждан, предприятий и организаций участвует в операциях с недвижимостью.
43608. Развитие внешнеэкономической деятельности в новосибирском транспортно – логистическом узле 1001.06 KB
  По суммарным показателям научно-промышленного, образовательного и культурного потенциала Новосибирск прочно занимает лидирующее положение в Сибири и третье место в России после Москвы и Санкт-Петербурга.