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

Лист

Изм.

Лист


 

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

9424. Задачи пропедевтической клиники. Понятие о семиотике. Общий план обследования больного. Расспрос больного. Общий осмотр больного 30.57 KB
  Задачи пропедевтической клиники. Понятие о семиотике. Общий план обследования больного. Расспрос больного. Общий осмотр больного Внутренние болезни - область клинической медицины, изучающая этиологию, патогенез и клинические проявления болезни ...
9425. Основные жалобы при заболеваниях органов дыхания 24.98 KB
  Основные жалобы при заболеваниях органов дыхания: Кашель - важный защитный механизм очищения бронхов от избыточного накапливающегося секрета. Возникает при раздражении рецепторов блуждающего нерва и кашлевых рефлексогенных зон - слизистая ...
9426. Последовательность топографической перкуссии 27.69 KB
  Последовательность топографической перкуссии Определение высоты расположения верхушек легких спереди Сзади Определение нижних границ легких по вертикальным линиям Определение экскурсии нижнего легочного края по вертикальным л...
9427. Семиотика заболеваний систем органов 19.46 KB
  Семиотика заболеваний систем органов Синдром компрессионного ателектаза Сдавление легкого извне плевральным выпадом или кровью, находящейся в плевральной полости(гидроторакс), сдавление воздухом (пневмоторакс), или опухолью Патогенез. Вздушность уме...
9428. Исследование больных с патологией ССС. Расспрос и осмотр. Пальпация прекардиальной области 31.21 KB
  Исследование больных с патологией ССС. Расспрос и осмотр. Пальпация прекардиальной области. Болезни сердца и сосудов в развитых странах занимают 1 место в структуре смертности населения. История кардиологии Боткин Сергей Петрович 1...
9429. Аускультация сердца. Тоны сердца в норме и патологии 28.68 KB
  Аускультация сердца. Тоны сердца в норме и патологии. Правила аускультации: Проводится после расспроса, осмотра, пальпации, перкуссии сердца. Сердце выслушивают (если позволяет состояние больного) стоя, сидя, лежа на левом боку, на право...
9430. Аускультация сердца. Сердечные шумы 28.02 KB
  Аускультация сердца. Сердечные шумы. Сердечные шумы - это более продолжительные высокочастотные звуки, с частотой 400-1000 Гц, которые возникают при деятельности сердца. Шум возникает в результате турбулентного тока при прохождении крови через ...
9431. Электрокардиография ЭКГ 29.49 KB
  Электрокардиография ЭКГ представляет собой графическое изображение колебаний электрических потенциалов, снятых с поверхности тела Самый распространенный и массовый инструментальный вид исследования. ЭКГ - колебание электрических потенци...
9432. Нарушение сердечного ритма 26.55 KB
  Нарушение сердечного ритма Аритмии являются наиболее распространенными нарушениями сердечного ритма. Их частота не поддается точной оценке. Приходящие нарушения ритма встречаются у большинства здоровых людей. При возникновении заболеваний внутренних...