Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Сортування даних - пірамідальне сортування

Название: Сортування даних - пірамідальне сортування
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 15:00:00 27 февраля 2011 Похожие работы
Просмотров: 2115 Комментариев: 2 Оценило: 2 человек Средний балл: 3.5 Оценка: неизвестно     Скачать

Зміст

Зміст

Постановка задачі

Теоретичні відомості

Вхідні – вихідні дані

Математичний розв’язок

Схема алгоритму програми

Алгоритм процедури введення даних

Алгоритм процедури виведення результатів сортування

Алгоритм процедури побудови дерева

Алгоритм процедури перестановки елементів

Алгоритм процедури «вирішення сімейного конфлікту»

Контрольний приклад для масиву з 20 елементів

Побудова піраміди

Сортування

Опис використаних в реалізації методу процедур та функцій

Користувацьке вікно ( форма )

Текст програми

Список використаної літератури


Постановка задачі

Відсортувати масив з 20 елементів, використовуючи пірамідальне сортування.

Теоретичні відомості

Сортування даних – це обробка інформації , в результаті якої її елементи розташовуються в заданій послідовності , в залежності від значення деяких ознак елементів цієї інформації.

Найбільш поширеним видом сортування є впорядкування масиву.

Задача сортування полягає в перестановці елементів послідовності в визначеному порядку. Впорядкування здійснюється в процесі багаторазового перегляду вхідного масиву. Методи сортування діляться на два класи :

1) Внутрішнє сортування, коли працюють з даними в оперативній пам’яті з довільним доступом;

2) Зовнішнє сортування , коли впорядковують інформацію, розташовану на зовнішніх носіях.

Алгоритм пірамідального сортування HeapSort використовує представлення масиву у виді дерева. Цей алгоритм не вимагає допоміжних масивів, сортуючи “на місці”. Розглянемо спочатку метод представлення масиву у виді дерева:

Нехай A[1 .. n] - деякий масив. Зіставимо йому дерево, використовуючи наступні правила:

1. A[1] - корінь дерева ;

2. Якщо A[i] - вузол дерева і 2i , то A[2*i] - вузол - “лівий син” вузла A[i]

3. Якщо A[i] - вузол дерева і 2i + 1 , то A[2*i+1] - вузол - “правий син” вузла A[i]

Правила 1-3 визначають у масиві структуру дерева, причому глибина дерева не перевершує [log2 n] + 1. Вони ж задають спосіб руху по дереву від кореня до листків. Рух вгору задається правилом 4:

4. Якщо A[i] - вузол дерева та i > 1, то A[i mod 2] - вузол - “батько” вузла A[i];

Вхідні – вихідні дані

Для роботи з даною програмою та алгоритму пірамідального сортування взагалі, нам необхідно ввести елементи масиву визначеної довжини, який необхідно відсортувати.

В результаті роботи програми ми отримаємо відсортований масив введених елементів.

Вхідні дані

Вихідні дані

Розмір вхідного масиву «N»

Масив з «N» елементів, елементи – цілі числа ( Масив A[1..N] – невпорядкований ).

Впорядкований масив з «N» елементів, елементи – цілі числа , кожен елемент масиву більше або дорівнює попередньому (Масив A[1..N] ; A[i]<= A[i+1]).

Математичний розв’язок

Алгоритм пірамідального сортування працює в два етапи:

I. Побудова сортуючого дерева;

II. Просіювання елементів по сортуючому дереву.

Як на I-ому, так і на II-ому етапах елементарна дія алгоритму полягає в вирішенні сімейного конфлікту: якщо найбільший із синів більше, ніж батько, то переставляються батько і цей син (процедура Swap).

У результаті перестановки може виникнути новий конфлікт у тому трикутнику, куди переставлений батько. У такий спосіб можна говорити про конфлікт (роду) у піддереві з коренем у вершині i. Конфлікт роду вирішується послідовним вирішенням сімейних конфліктів проходом по дереву вниз. Конфлікт роду вирішено, якщо прохід закінчився (i > n div 2), або ж в результаті перестановки не виник новий сімейний конфлікт (процедура Conflict).

I етап – побудова сортуючого дерева - оформимо у виді рекурсивної процедури, використовуючи визначення:

Якщо ліве і праве піддерева ( T[2i] і T[2i+1] ) дерева T[i] є сортуючими, то для перебудови T[i] необхідно вирішити конфлікт роду в цьому дереві.

II етап - етап просіювання - для k від n до 2 повторюються наступні дії:

1.Переставити A[1] і A[k];

2.Побудувати сортуюче дерево початкового відрізка масиву A[1..k-1], усунувши конфлікт роду в корені A[1]. Відзначимо, що 2-а дія вимагає введення в процедуру Conflict параметра k.

Нескладно підрахувати, що С(n) = O( n log2 n ), М(n) = O( n log2 n )

Схема алгоритму програми


Алгоритм процедури введення даних

Алгоритм процедури виведення результатів сортування


Алгоритм процедури побудови дерева

Алгоритм процедури перестановки елементів

b = a[i]

a[i] = a[j]

a[j] = b

Алгоритм процедури «вирішення сімейного конфлікту»


Контрольний приклад для масиву з 20 елементів

Побудова піраміди






Сортування





















алгоритм програма елемент вікно

Опис використаних в реалізації методу процедур та функцій

Процедура Swap

Procedure Swap(i, j : Integer)

Переставляє місцями елементи масиву A[i] та A[j] за умови , якщо A[i] < A[j].

Процедура Conflict

Procedure Conflict(i, k : Integer)

Вирішує сімейний конфлікт у дереві : якщо найбільший із синів більше, ніж батько, то переставляються батько і цей син (процедура Swap).

Процедура SortTree

Procedure SortTree(i : Integer)

Будує сортуюче дерево за правилами :

1. A[1] - корінь дерева ;

2. Якщо A[i] - вузол дерева і 2i , то A[2*i] - вузол - “лівий син” вузла A[i]

3. Якщо A[i] - вузол дерева і 2i + 1 , то A[2*i+1] - вузол - “правий син” вузла A[i]

Правила 1-3 визначають у масиві структуру дерева, причому глибина дерева не перевершує [log2 n] + 1. Вони ж задають спосіб руху по дереву від кореня до листків. Рух вгору задається правилом 4:

4. Якщо A[i] - вузол дерева та i > 1, то A[i mod 2] - вузол - “батько” вузла A[i].

Процедура Show_result

Procedure Show_result

Виводить в циклі елементи відсортованого масиву на екран.

Процедура get_data

Procedure get_data

Зчитує значення елементів масиву для сортування.

Користувацьке вікно ( форма )


Текст програми

var

Form1: TForm1;

A:array[1..20] of real;

N,k:integer;

implementation

Procedure Swap(i, j : Integer);

Var b : Real;

Begin

If a[i] < a[j] then

begin

b := a[i];

a[i] := a[j];

a[j] := b

end

End;

Procedure Conflict(i, k : Integer);

Var j : Integer;

Begin

j := 2*i;

If j = k then

Swap(i, j)

else

if j < k then

begin

if a[j+1] > a[j] then

j := j + 1;

Swap(i, j);

Conflict(j, k)

End End;

Procedure SortTree(i : Integer);

begin

If i <= n div 2 then

begin

SortTree(2*i);

SortTree(2*i+1);

Conflict(i, n)

end

end;

procedure Show_result;

var i:integer;

begin

Form1.label1.Caption:='';

for i:=1 to N do

begin

Form1.Label1.Caption:=Form1.Label1.Caption+' '+floattostr(A[i]);

Form1.stringGrid1.Cells[i-1,0]:=floattostr(A[i]);

end; end;

procedure get_data;

var i:integer;

begin

for i:=1 to N do

begin

if Form1.StringGrid1.Cells[i-1,0]<>'' then

try

A[i]:=strtoint(Form1.StringGrid1.Cells[i-1,0])

except on EConvertError do showmessage('Недопустимый формат данных ! Присвоено значение "0"'); end

else

showmessage('Обнаружено пустое поле ! Присвоено значение "0"');

end;

end;

procedure TForm1.BitBtn1Click(Sender: TObject);

var i:integer;

begin

get_data;

Label1.Caption:='';

Label1.Enabled:=true;

SortTree(1);

For k := n downto 2 do

begin

Swap(k, 1);

Conflict(1, k - 1) end;

show_result; end;

procedure TForm1.Button1Click(Sender: TObject);

begin

try

N:=strtoint(edit1.Text);

except on EConvertError do

edit1.Clear end;

Form1.Height:=250;

label1.visible:=true;

stringGrid1.Visible:=true;

bitbtn1.Visible:=true;

stringGrid1.ColCount:=n;

stringGrid1.RowCount:=1;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Form1.Height:=120; end; end

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:49:02 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
09:52:57 29 ноября 2015

Работы, похожие на Курсовая работа: Сортування даних - пірамідальне сортування

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(149903)
Комментарии (1829)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru