43255

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

Курсовая

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

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

Русский

2013-11-04

211 KB

8 чел.

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

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

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

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

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

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

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

(ИТ - 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

Лист

Изм.

Лист


 

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

51353. Решение системы линейных уравнений методом Гаусса 158 KB
  Руководство программиста Описание структуры программы Функции PHod осуществляет прямой ход; OHod осуществляет обратный ход; Описание структур данных Описание глобальных переменных использующихся в программе: int n размер матрицы; flot rr массив в котором хрантся элементы матрицы; flot ms копия масива rr; flot x массив решений системы уравнений; FILE file файл из которого берется матрица; FILE file2 файл в который записываются результаты; Описание алгоритмов Метод Гаусса для решения системы линейных...
51354. КОРРЕКЦИЯ ЗАМКНУТОЙ САУ 200.72 KB
  Определение характеристик разомкнутой системы 1. Собрать схему исследования разомкнутой системы автоматического регулирования. Сделать вывод об устойчивости или неустойчивости замкнутой системы построенной на основе такой разомкнутой системы. По величине запаса фазы определить тип переходной характеристики замкнутой системы полученной на основе анализируемой разомкнутой системы колебательная апериодическая близкая к апериодической с небольшим перерегулированием.
51357. Анализ информационных систем на CMS, обладающих редакцией для корпоративных порталов и удовлетворяющих требованиям сотрудников компаний для работы в коллективе 582.04 KB
  Из всего выше сказанного можно заключить что аудиторией информационной системы будут сотрудники компании занимающейся веб разработкой и внедрившей корпоративный портал.2 Обзор систем аналогов Среди аналогов проектируемой системы в России можно выделить три крупных компаний разрабатывающих CMS которые имеют редакции корпоративный портал и отвечающие требованиям работников компании. Из многочисленных достоинств системы можно выделить: наличие огромного количества модулей которые могут удовлетворить желания большого количества фирм;...
51358. Расчет системы безопасности ООО НПО «Магистраль-Инжиниринг» 101.5 KB
  Источник угрозы безопасности информации – субъект доступа, материальный объект или физическое явление, являющиеся причиной возникновения угрозы безопасности информации.
51359. Синдромное декодирование 46.8 KB
  На основе кода с проверкой на четность можно построить высокоскоростной код позволяющий исправлять однократные ошибки где проверки на четность располагаются оптимальным образом код Хэмминга. Так уравнения для формирования проверочных символов могут быть представлены в виде порождающей матрицы G а для проверок на четность в виде проверочной матрицы кода H. Ход работы В ходе данной лабораторной работы было реализовано консольное приложение которое выполняет следующие функции: 1строит порождающую и проверочную матрицы для кода...
51360. Анализ показателей кадровой работы ТЧЭ-2 485 KB
  Данная работа представляет собой отчет по производственной практике на предприятии Эксплуатационное локомотивное депо Красноярск-Главный (далее ТЧЭ-2). Общая характеристика предприятия.3 Организационная структура предприятия. Социальный паспорт предприятия. Анализ показателей работы предприятия.
51361. Красноярский территориальный центр фирменного транспортного обслуживания 61.42 KB
  Сокращенное наименование Подразделения: Красноярский ТЦФТО ОАО РЖД. Подразделение для организации и осуществления своей деятельности открывает расчетный счет ОАО РЖД в банках и иных кредитных организациях в порядке установленном законодательством Российской Федерации внутренними документами ОАО РЖД Филиала. Подразделение имеет круглую печать содержащую его сокращенное наименование указание на его место нахождения а также полное фирменное наименование ОАО РЖД. Подразделение может иметь штампы и бланки со своим наименованием...