WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Демонстрація сортування методом спливаючих бульбашок - Курсова робота

Демонстрація сортування методом спливаючих бульбашок - Курсова робота

1
2 2 2 2 1
4 4 4 3 2
8 8 7 6 4
16 15 14 12 8
........
Зрозуміло, що якщо розподіл заснований на числі Фібоначчі fi, то мінімальне число серій в допоміжних файлах буде рівне fi, а максимальне - f(i+1). Тому після виконання злиття ми отримаємо максимальне число серій - fi, а мінімальне - f(i-1). На кожному етапі виконуватиметься максимально можливе число злиття, і процес зійдеться до наявності всього однієї серії.
Оскільки число серій в початковому файлі може не забезпечувати можливість такого розподілу серій, застосовується метод додавання порожніх серій, які надалі якомога більш рівномірного розподіляються між проміжними файлами і пізнаються при подальшому злитті.
Зрозуміло, що ніж менше таких порожніх серій, тобто чим ближче число початкових серій до вимог Фібоначчі, тим більше ефективно працює алгоритм.
Сортування за допомогою дерева
Почнемо з простого методу сортування за допомогою дерева, при використовуванні якого будується двійкове дерево порівняння ключів. Побудова дерева починається з листків, яке містить всі елементи масиву. З кожної сусідньої пари вибирається найменший елемент, і ці елементи утворюють наступний (ближче до кореня рівень дерева). З кожної сусідньої пари вибирається якнайменший елемент і т.д., поки не буде побудований корінь, якнайменший елемент масиву, що містить. Отже, ми вже маємо якнайменше значення елементів масиву. Для того, щоб отримати наступний по величині елемент, спустимося від кореня по шляху, що веде до листа з якнайменшим значенням. В цій листовій вершині проставляється фіктивний ключ з "нескінченно великим значенням", а у все проміжні вузли,
що займалися якнайменшим елементом, заноситься якнайменше значення з вузлів - безпосередніх нащадків . Процес продовжується до тих пір, поки всі вузли дерева не будуть заповнені фіктивними ключами .
На кожному з n кроків, що вимагаються для сортування масиву, потрібно log n (двійковий) порівнянь. Отже, всього буде потрібно
log n порівнянь, але для представлення дерева знадобиться 2n - 1 додаткових одиниць пам'яті.
Є досконаліший алгоритм, який прийнято називати пірамідальним сортуванням . Його ідея полягає в тому, що замість повного дерева порівняння початковий масив а[1], а[2] ..., а[n] перетвориться в піраміду, що володіє тією властивістю що для кожного а[i] виконуються умови а[i]<= а[2i] і а[i]= а[2?i] і а[1]>= а[2?i+1] для всіх осмислених значень індексу i.
Сортування за допомогою піраміди
Початкова піраміда 1 6 5 23 44 33 8 65
Крок 1 65 6 5 23 44 33 8 1
5 6 65 23 44 33 8 1
5 6 8 23 44 33 65 1
Крок 2 65 6 8 23 44 33 5 1
6 65 8 23 44 33 5 1
6 23 8 65 44 33 5 1
Крок 3 33 23 8 65 44 6 5 1
Процедура сортування з використанням піраміди вимагає виконання порядку nx log n кроків (логарифм - двійковий) у гіршому разі, що робить її особливо привабливою для сортування великих масивів.
1.5. Порівняльна характеристика методів сортування.
Пригадаємо один з простих методів - метод підрахунку. Оскільки цей метод, не дивлячись на удосконалення, вимагає порівняння всіх пар елементів, то тривалість сортування масиву з n елементів буде пропорційна n2. Дещо кращі показники мають методи сортування вставками, обміном і вибором, проте і в них тривалість роботи процедур також пропорційна n2. Разом з тим можна показати, що час, затрачуваний на впорядковування масиву такими методами, як, наприклад, швидке сортування або пірамідальне сортування, пропорційно n log2n, тобто значно менше. Тому всі розглянуті методи сортування розділяють на прості (n2) і вдосконалені, або "логарифмічні" (n log2n) .
Показники для оцінки того або іншого методу в використовуються кільксть порівнянь і кількість переміщень елементів в ході сортування. Проте ці характеристики не враховують витрат часу на інші операції, такі, як управління циклами, і ін. Очевидно, що критерієм для порівняння різних методів є час, затрачуваний на сортування.
Н.Вірт відзначає також наступне:
- "сортування методом бульбашки" є найгіршим серед всіх порівнюваних методів. Її поліпшений варіант - "шейкер" - сортування.
- все-таки гірше, ніж сортування простими вставками і сортування вибором;
- особливістю швидкого сортування є те, що вона сортує масив з елементами, розташованими в зворотному порядку практично так само, як і відсортований в прямому порядку. Слід додати, що приведені результати були отримані при сортуванні числових масивів. Якщо ж значенням елементів масиву є дані типу "запис", в яких супутні поля (компоненти) займають в 7 разів більше пам'яті, ніж числове поле, по якому проводиться сортування, то картина зміниться.
II Алгоритм реалізації проекту
2.1.Підготовча робота
Вікно програми умовно розділимо на дві частини:
" Частина де буде виводитись інформація про принцип сортування методом "бульбашки";
" Частина буде виконуватися сортування даних які ввів користувач.
Інформація про принцип сортування буде знаходитись в текстовому файлі під назвою "text.txt".
2.2.Розробка частини про принцип сортування.
Виведення інформації про сортування буде отримуватися з текстового файлу за допомогою даних операторів:
AssignFile(f,'text.txt');
Reset(f);
Які розміщенні в обробнику події onCreate форми програми, та
Readln(f,s)- який в змінні s присвоює наступну стрічку тексту.
Виведення на екран буде виконуватися таймером , текст із змінної s буде поміщатися в компоненти Label, при чому значення властивості Caption наступного компонента Label буде присвоюватися занченню попереднього компонента що створить ефект титрів:
procedure TForm1.Timer1Timer(Sender: TObject);
var
s:string;
begin
Readln(f,s);
if s='' then Timer1.Enabled:=False;
Label1.Caption:=Label2.Caption;
Label2.Caption:=Label3.Caption;
Label3.Caption:=Label4.Caption;
Label4.Caption:=Label5.Caption;
Label5.Caption:=Label6.Caption;
Label6.Caption:=Label7.Caption;
Label7.Caption:=Label8.Caption;
Label8.Caption:=s;
end;
Для більш ефектнішого подання теорії в програмі реалізуємо ефект появлення і зникнення з форми, тобто колір тексту трьох перши і троьох останіх компонентів Label будуть розміщені в кольоровій гамі між кольором форми та чорним кольором.
Label1.Font.Color:=rgb(200,190,198);
Label2.Font.Color:=rgb(120,110,96);
Label3.Font.Color:=rgb(45,54,50);
Label6.Font.Color:=rgb(45,54,50);
Label7.Font.Color:=rgb(120,110,96);
Label8.Font.Color:=rgb(200,190,198);
Можливий варіант коли користувач не повністю зрозумів, а бо просто пропустив теоретичні частину, для цього реалізуємо можливість ще раз продивитись текст:
var
i:integer;
Com:TComponent;
begin
Reset(f);
for i:=1 to 8 do
begin
Com:=FindComponent('Label'+inttostr(i));
(Com as TLabel).Caption:='';
end;
Timer1.Enabled:=True;
Спочатку перейдемо на початок файлу, щоб виводити інформацію спочатку.
В наступних операторах очистимо всі компоненти Label,запустивши цикл будемо шукати компоненти з назвою, яка складається з Label та номеру який генерується циклом , знайдений компонент буде розглядатися як компонент типу TLabel та властивість Caption буде ощищуватися, та запустимо таймер для виводу тексту.
Для зупинки виведення тексту просо зупинимо
Loading...

 
 

Цікаве