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

Лист

Изм.

Лист


 

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

52328. Групові форми і методи навчання на уроках біології 155.5 KB
  Тому в сучасній системі України головною метою навчання біології є інтелектуальний розвиток учнів засобами навчального предмету формування особистостей виховання громадян демократичного суспільства закладання підвалин екологічного стилю мислення підготовка до життя у високотехнологічному суспільстві. В умовах оновлення системи шкільної освіти і біології зокрема розроблено проект концепції що передбачає різнорівневе навчання впроваджуються нові навчальні технологи створюються нові програми підручники та навчальні посібники....
52329. Впровадження інноваційних технологій на уроках біології з використанням опорних конспектів 401.5 KB
  Посібник містить методичні ідеї використання опорних конспектів на уроках біології, питання впровадження інноваційних технологій на уроках біології в умовах модернізації освіти, систему уроків з використанням структурно-логічних схем та логічно-опорних сигналів (СЛС та ЛОС ) з теми «Вступ у ботаніку»
52330. Абсорбционная установка 412 KB
  В абсорбционных процессах (абсорбция, десорбция) участвуют две фазы —жидкая и газовая и происходит переход вещества из газовой фазы в жидкую при абсорбции) или, наоборот, из жидкой фазы в газовую (при десорбции). Таким образом, абсорбционные процессы являются одним из видов процессов массопередачи.
52332. Впровадження інноваційних технологій у формуванні компетентного учня на уроках біології 71 KB
  Умовами їх використання є: створення психологічного клімату на уроці наявність соціальних навичок уміння учнів спілкуватися бажання вчителя спілкуватися з учнями “на рівних “. 1 Я переконалась що застосування інтерактивних технологій є результативнішим в порівнянні з пасивними методами навчання: у моїх учнів краще розвиваються комунікативні вміння і навики; вони навчилися краще працювати в команді прислухатися до думки кожного; діти удосконалили вміння шукати і аналізувати інформацію захищати...
52333. Органические соединения: микро- и макромолекулы. Углеводы: строение, свойства, функции 57 KB
  Цели урока: содействовать формированию у учащихся понятий макро и микромолекулы органические соединения; обеспечить условия для углубления знаний о роли углеводов в живом организме о связи между строением и свойствами углеводов; создать условия для формирования у учащихся общеучебных приемов и способов учебной деятельности: умения составлять схемы и таблицы работать с учебником и дополнительной литературой использовать данные экспериментов работать индивидуально и в группах; умение решать проблемные вопросы. Чтобы ответить на...
52334. Неклітинні форми життя – віруси 3.48 MB
  Мета: вивчити будову, властивості, механізм проникнення вірусів у клітину. Зясувати роль вітчизняних вчених у розвиток вірусології. Розвивати у учнів комунікативну та самоосвітню компетентність. Виховувати повагу до свого здоров’я.
52336. АЛГОРИТМ ФОРМУВАННЯ ВМІНЬ ВИКОРИСТОВУВАТИ ЗНАННЯ ПРИ РОЗВ’ЯЗАННІ ТИПОВИХ ЗАДАЧ З МОЛЕКУЛЯРНОЇ БІОЛОГІЇ 309.5 KB
  ПРИКЛАДИ РОЗВ’ЯЗАННЯ ЗАДАЧ НА МОЛЕКУЛЯРНІ ОСНОВИ СПАДКОВОСТІ Під час розв’язання таких задач необхідно пам’ятати що: довжина одного нуклеотида або відстань між двома сусідніми вздовж осі ДНК становить 034 нм; середня молекулярна маса одного нуклеотида 345 умовних одиниць; середня молекулярна маса однієї амінокислоти дорівнює 100 умовних одиниць; молекула білка в середньому складається з 200 амінокислот; кожну амінокислоту в білковій молекулі кодує триплет нуклеотидів іРНК під час трансляції; для визначення довжини гена l...