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

Лист

Изм.

Лист


 

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

41617. Приближённое решение задачи Коши методами Эйлера и Рунге-Кутта 97.24 KB
  Решить на отрезке с шагом задачу Коши для системы второго порядка = Требуется использовать: метод Эйлера метод Рунге-Кутта Теория: 1 Метод Эйлера Пусть требуется найти приближённое решение дифференциального уравнения удовлетворяющее начальному условию. Чаще всего 1 Этот метод относится к группе одношаговых методов в которых для расчёта точки...
41618. Автоматизация кодирования графа переходов 145 KB
  В результате выполнения данной лабораторной работы я приобрёл навыки по автоматизации соседнего кодирования графа переходов автомата Мили. Соседнее кодирование реализовано по алгоритму, описаному выше...
41619. Текстовий редактор 122.58 KB
  Лістинг програми fn=String::Empty; textChnged=flse; } prgm endregion privte: System::Void копіюватиToolStripMenuItem_ClickSystem::Object^ sender System::Eventrgs^ e { textBox1 Copy; } privte: System::Void копіюватиToolStripMenuItem1_ClickSystem::Object^ sender System::Eventrgs^ e { textBox1 Copy; } privte: System::Void вирізатиToolStripMenuItem_ClickSystem::Object^ sender System::Eventrgs^ e { textBox1 Cut; } privte: System::Void...
41620. Решение задачи Дирихле для уравнения Пуассона методом Чебышева 103.07 KB
  Разностную задачу 5 будем решать явным итерационным методом с чебышевским набором параметров который выражается следующей формулой: 10 где заданное число итераций . 11 Результаты: В вычислениях использовался следующий алгоритм: Задаём количество итераций полагаем тогда шаг сетки =01. Полученный ответ с точностью до...
41621. Генерация таблицы переходов и функций возбуждения тригеров 141.5 KB
  В результате выполнения данной лабораторной работы я приобрёл навыки анализа графовых структур и автоматизации процедуры построения таблицы переходов. Мной был разработан класс для генерации таблицы переходов.
41622. Решение первой начальной краевой задачи для уравнения теплопроводности по схеме Кранка-Николсона 102.29 KB
  Задача: Используя метод простых итераций метод Чебышева и метод наискорейшего спуска найти по схеме КранкаНиколсона приближенное решение задачи: 1 2...
41623. Дослідження структури поля в металевих хвилеводах і резонаторах 179.46 KB
  Київ 2010 Мета роботи – дослідити розподіл електромагнітного поля в призматичних та циліндричних хвилеводах та резонаторах методом електричного зонду. Структура поля досліджується за допомогою електричного зонду з детекторною голівкою.
41624. Робота з операторами INSERT, UPDATE, DELETE 47.12 KB
  VLUES із списком з декількох значень підтримується у версії MySQL 3. Синтаксис виразу col_nme=expression підтримується у версії MySQL 3. У MySQL завжди передбачено значення за умовчанням для кожного поля. Ця вимога нав'язана MySQL щоб забезпечити можливість роботи як з таблицями які підтримують транзакції так і з таблицями що не підтримують їх.
41625. Створення резервної копії та відновлення даних з неї 218.34 KB
  Вибрати базу даних. У вікні Загрузка файла вибрати Сохранить та вказати місце на диску для збереження дампу бази даних. Відновлення бази даних за допомогою програми phpMydmin Щоб виконати відновлення бази даних потрібно: Вилучити існуючу базу даних.