Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Об’єктна модель в С++. Прості методи сортування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Програмування частина 4 Технологія системного програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Інститут дистанційного навчання
Кафедра СКС
КУРСОВА РОБОТА
з дисципліни «Програмування»
на тему «Об’єктна модель в С++. Прості методи сортування»
Варіант № 19
Завдання на курсову роботу:
1. Провести огляд методів сортування масивів, що широко застосовуються у програмуванні. Розглянути їх властивості і практичне значення.
2. Написати програму, що реалізує один з простих методів сортування: пpоцедуpи соpтування методами Шелла, пірамідального та швидкого соpтування мiстяться у файлах.
3. Згенерувати три масиви з випадковими елементами типу Integer довжиною 100, 1000 та 10000 елементів, відповідно.
4. Відсортувати одержані масиви за збільшенням елементів, визначивши при цьому такі параметри:
кількість порівнянь;
кількість обмінів;
фактичний час роботи,
необхідні кожній з програм (простий та один з довершених методів), щоби відсортувати кожен з трьох масивів.
ЗМІСТ
ВСТУП………………………………………………………………………..
4
1.
Основні поняття об’єкт-орієнтованого програмування……………....
5
2.
Особливості об’єктної моделі в С++…………………………………...
8
3.
Ініціалізація і знищення об’єктів. Конструктори і деструктори……..
10
4.
Динамічний розподіл пам’яті ………………………………………….
12
5.
Елементарні методи сортування……………………………………….
14
5.1
Сортування вибором…………………………………………………….
17
5.2
Сортування вставкою…………………………………………………..
18
5.3
Бульбашкове сортування……………………………………………….
19
5.4
Характеристики найпростіших сортувань…………………………….
19
5.5
Сортування файлів з великими записами……………………………..
19
5.6
Сортування Шелла……………………………………………………..
20
6.
Практична реалізація простих методів сортування………………….
21
ВИСНОВКИ…………………………………………………………………
28
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ……………………………..
29
ВСТУП
В зв’язку з швидким розвитком обчислювальної техніки широкого розповсюдження при проведенні наукових досліджень та інженерного проектування набув обчислювальний експеримент. Обчислювальний експеримент базується на побудові та аналізі за допомогою ЕОМ математичних моделей досліджуваного об’єкту.
Розглянемо схему обчислювального експерименту (рис. 1.1).
Рис. 1.1. Схема обчислювального експерименту
Нехай необхідно дослідити якийсь об’єкт, явище або процес (1). Тоді спочатку формулюються основні закони та взаємозв’язки, що описують даний об’єкт. На їх основі розробляється математична модель (2), що являє собою, як правило, запис цих законів у вигляді системи рівнянь (алгебраїчних, диференціальних, інтегральних і т.д.). Після того, як задачу cформульовано, її необхідно розв’язати. Тільки в досить простих випадках вдається отримати розв’язок у явному вигляді. В більшості випадків виникає необхідність використання того чи іншого наближеного методу (обчислювального методу або дискретної моделі). На основі отриманої дискретної моделі будується обчислювальний алгоритм, результатом реалізації якого є число або таблиця чисел.
Для реалізації обчислювального методу необхідно розробити програму для ЕОМ (4). Після розробки та відладки програми наступає етап проведення обчислень (5). Отримані результати детально аналізують (6) з точки зору їх відповідності досліджуваному явищу і, при необхідності вносяться зміни в математичну модель або обирається інший обчислювальний метод. Цей цикл повторюється доти, доки не буде отримано результати з необхідною точністю.
1. ОСНОВНІ ПОНЯТТЯ ОБ’ЄКТНО-ОРІЄНТОВАНОГО ПРОГРАМУВАННЯ
Моделювання процесів реального світу є досить складною задачею, оскільки модель повинна відповідати багатьом вимогам, а саме:
- відображати процеси, що моделюються з високою точністю;
- мати однозначну відповідність між параметрами системи і фізичними
процесами;
- бути достатньо простою для реалізації.
Ці вимоги є досить суперечливими. Так, наприклад, моделі, що відображають явища з високою точністю можуть бути занадто складними і потребувати занадто великих машинних ресурсів. Тому при моделюванні реальних явищ користуються спрощеними моделями, які враховують лише ті особливості системи, що є найбільш загальними і значущими для даної системи, або іншими словами використовують певний рівень абстрагування.
При цьому, в процесі моделювання, розроблюються структури даних, що характеризують дане явище чи систему. Ці структури даних формуються з урахуванням рівня абстрагування і доступних можливостей засобів розробки, а саме мови програмування, апаратної бази, операційної системи і т.д. Такі структури даних називаються абстрактними типами даних.
Для програмної реалізації абстрактних типів даних в мові програмування С++ використовується об'єктно-орієнтоване програмування (ООП).
Основна ідея об'єктно-орієнтованого програмування полягає в об'єднанні даних і алгоритмів для їх обробки в єдине ціле[3], єдину інформаційну структуру, єдиний тип даних. Цей тип даних специфікує члени-дані, звані полями, і операції для роботи з цими даними, звані методами. Поля описують параметри та характеристики системи, а методи описують поведінку системи, а саме взаємозв’язок між параметрами системи та реакції системи на вплив зовнішніх по відношенню до неї чинників.
Наприклад нам необхідно написати програму, що моделює поведінку системи, яка складається з пружини, закріпленої одним кінцем до стелі, і тягарця закріпленого на вільному кінці пружини. Нехай нас цікавить положення тягарця в залежності від його маси , параметрів пружини та прикладеної зовнішньої сили. Для простоти будемо розглядати одновимірний випадок, коли зміщення тягарця може відбуватись лише вздовж осі пружини. Тоді абстрактний тип даних, що описує дану систему повинен містити для збереження параметрів системи наступні поля – змінну для збереження маси тягарця, змінні для збереження жорсткості пружини та довжини пружини у вільному стані, змінну для збереження величини зовнішньої сили. Також цей тип даних повинен містити функцію, яка вираховує положення тягарця в залежності від величини вищевказаних змінних, а також додаткові (службові) функції для встановлення потрібних значень вищевказаних змінних і відображення результатів розрахунку.
Концепція ООП базується на наступних принципах:
- абстрагування;
- інкапсуляція;
- успадкування;
- поліморфізм;
- повторне використання коду.
Дамо означення цих принципів.
Абстрагування – це виділення найбільш загальних і значимих особливостей досліджуваної системи з метою спрощення результуючої моделі. Результатом абстрагування є розроблення абстрактного типу даних.
Інкапсуляція – це поєднання в одній абстрактній інформаційній структурі даних (полів) та алгоритмів їх обробки (методів).
Успадкування – це засіб побудови нових (породжених) абстрактних інформаційних структур на основі уже існуючих (базових). При цьому породжені структури утворюються шляхом додавання нових полів та методів або шляхом модифікації існуючих і можуть успадковувати деякі або всі властивості базових структур. Це дозволяє повторно використовувати існуючий програмний код і, за рахунок цього, прискорити розробку програмного забезпечення. Породжені структури називають потомками, а базові – предками.
Розглянемо приклад. Нехай існує інформаційна структура яка описує фігуру трикутник, а нам треба побудувати структуру, що описує чотирикутник. Тоді, використовуючи успадкування, нам достатньо до структури трикутника додати ще дві змінних, які описують положення четвертої вершини, а також замінити процедуру відображення фігури на екрані. При цьому змінні, які описують положення перших трьох вершин, будуть успадковані від структури трикутник, і нам не треба буде витрачати час на їх реалізацію.
Поліморфізм – властивість інформаційної структури, яка полягає у можливості зміни її поведінки у залежності від того з якими іншими структурами вона взаємодіє.
Типовим прикладом є реалізація арифметичних операторів у мовах програмування, коли їх застосування до цілих чисел виконується за правилами цілочисельної математики, а їх застосування до чисел з плаваючою комою за іншими правилами. При цьому вибір правил відбувається автоматично. Звісно, що така можливість повинна бути закладена до інформаційної структури на етапі її розробки.
Повторне використання коду означає, що нові абстрактні типи можна не розроблювати з нуля. Нові типи даних можна розроблювати на основі вже існуючих. Для цього спочатку знаходять в бібліотеці тип (або типи даних), який (які) найбільше відповідає (відповідають) потребам, і модифікують, використовуючи механізми успадкування та поліморфізму.
Принципи об'єктно-орієнтованого програмування реалізовані по-різному в різних мовах програмування. Особливості реалізації ООП в мові програмування С++ будуть розглянуті далі.
2. ОСОБЛИВОСТІ ОБ’ЄКТНОЇ МОДЕЛІ В С++
Ключовим поняттям в об’єктно-орієнтованому програмуванні на С++ є поняття класу.
Клас в С++ – це практична реалізація абстрактного типу даних засобами мови програмування С++. Фактично клас – це визначений програмістом нестандартний тип даних, тому поняття полів і методів класу повністю співпадають з аналогічними поняттями абстрактного типу даних.
Процес визначення класу складається з двох частин.
Перша частина – це опис класу. В цій частині визначається структура класу, а саме кількість та типи полів(властивостей) класу, кількість методів, кількість та типи вхідних параметрів методів, а також типи результатів виконання методів. Крім того на цьому етапі визначається область видимості полів та методів.
Опис класу починається з ключового слова class, за яким слідує назва класу. Він складається з розділів, які виділяються модифікаторами public, private, protected, що є заголовками розділів і визначають їх початок та область бачимості полів та методів, розташованих у розділі.
У розділах із заголовками public розміщуються загальнодоступні поля та методи, які використовуються для інтерфейсу об’єктів даного класу з програмою. Доступ до цих полів і методів може бути здійснений прямим зверненням.
У розділах із заголовками private розміщуються закриті дані, доступ до яких може бути здійснений лише за допомогою методів самого класу або за допомогою друзів класу. Поняття друзів класу буде розглянуто пізніше.
Розділи із заголовками protected містять дані, доступ до яких може бути здійснений за допомогою методів самого класу, за допомогою методів породжених класів або за допомогою друзів класу.
Розділ починається заголовком та закінчується заголовком іншого розділу або межею опису класу. Опис класу обмежується заголовком класу та фігурними скобками. „{”, „}”. Кількість розділів не лімітується. Клас може складатися як з одного розділу, так із кількох, порядок розташування розділів довільний в межах опису класу. В описі класу може існувати кілька розділів з однаковими заголовками. Перший розділ опису класу може бути без заголовку. В цьому випадку вважається, що заголовком розділу є модифікатор private.
Друга частина визначення класу – це опис методів класу. В цій частині реалізуються засобами мови програмування алгоритми методів класу.
Обидві частини є обов’язковими при визначенні класу і жодна з них не може бути пропущена. Опис класу та опис методів класу повинні бути розміщені у одному файлі. Зазвичай їх розміщують у окремих файлах із розширенням „h” і потім включають за допомогою директиви #include до кожного з тих файлів проекту, в яких використовуються об’єкти даного класу.
Розглянемо приклад визначення класу.
Опис класу:
class MyClass
{
int i; //розділ із типом доступу private
public: //розділ із типом доступу public
int get_i();
void set_i(int);
};
Опис методів класу:
int MyClass::get_i() { return i; }
void MyClass::set_i(int x) { i=x; return; }
Якщо методи класу прості і складаються всього лише з кількох операторів, то їх опис можна розмістити прямо у описі класу.
class MyClass
{
int i; //розділ із типом доступу private
public: //розділ із типом доступу public
int get_i(){ return i; };
void set_i(int) { i=x; return; };
};
Для збільшення швидкодії програми при описі методів класу може використовуватись модифікатор inline (вбудований). Використання цього модифікатора зменшує кількість операцій процесора при визові таких функцій. Однак при цьому збільшується об’єм програми, тому такий модифікатор бажано використовувати тільки з невеликими методи, що складаються лише з кількох операторів. Як у нижченаведеному прикладі.
class MyClass
{
int i; //розділ із типом доступу private
public: //розділ із типом доступу public
inline int get_i(){ return i; };
inline void set_i(int) { i=x; return; };
};
Як було сказано вище клас – це абстрактний тип даних. Для того щоб використати розроблений клас у програмі необхідно об’явити змінну даного типу. Така змінна буде називатись об’єктом даного класу. Таким чином об’єкт класу – це конкретна змінна (екземпляр) класу (даного типу інформаційної структури).
Об’явити об’єкт даного класу можна таким же чином, як і змінну будь-якого іншого стандартного або заданого користувачем типу. Наприклад об’явити об’єкт показаного вище класу MyClass при умові, що даний клас описаний у файлі MyClass.h, який знаходиться у одному каталозі з проектом, можна наступним чином:
#include “MyClass.h”
…
MyClass MyObj;
3. ІНІЦІАЛІЗАЦІЯ І ЗНИЩЕННЯ ОБ’ЄКТІВ. КОНСТРУКТОРИ ТА ДЕСТРУКТОРИ
Створюючи і використовуючи такі складні інформаційні структури як класи, програміст потребує наявності ефективних засобів керування об’єктами. Для класа потрібен механізм, який визначає поведінку об’єкта при ініціалізації та знищенні, контролює розподіл пам’яті в процесі ініціалізації та знищенні об’єктів, щоб програміст міг використовувати об’єкти класів аналогічно змінним стандартних типів.
В С++ передбачена реалізація такого механізму шляхом використання конструкторів та деструкторів.
Конструктор – це функція метод класу з таким самим ім’ям, як у класу. Цей метод призначений для створення та ініціалізацію об’єктів класу, виділення пам’яті під об’єкти та присвоєння початкових значень полям об’єкту.
Деструктор – це функція метод класу, яка відповідає за коректне вивільнення пам’яті при знищенні об’єкту. Деструктор завжди має ім’я таке ж, що і у класу, перед яким ставиться символ „~”.
Конструктори і деструктори не можуть повертати значень і тому при їх описанні відсутній тип результату.
Конструктор може мати вхідні параметри, а може не мати.
Конструктор, який не має вхідних параметрів називається конструктором за замовчуванням.
Клас може не містити цих функцій у явному вигляді. Тоді розподіл пам’яті та ініціалізація об’єкту виконуються системою автоматично стандартним шляхом. Але оскільки стандартна процедура не враховує особливостей класу, то така процедура може бути неефективною і часто навіть може призводити до серйозних помилок в роботі програми, тому бажано при розробці класів розробляти конструктори та деструктори. Клас може мати кілька конструкторів і лише один деструктор. Для прикладу добавимо конструктор в розглянутий вище клас MyClass.
class MyClass
{
int i; //розділ із типом доступу private
public: //розділ із типом доступу public
MyClass(){i=0;}//Конструктор. У описі відсутній тип результату.;
//Вхідні параметри відсутні. Це конструктор за замовчуванням;
inline int get_i(){ return i; };
inline void set_i(int) { i=x; return; };
};
В даному випадку конструктор дуже простий і не потребує параметрів при визові. Це конструктор по замовчуванню. Розглянемо більш складний
приклад.
class MyClass
{
int i; //розділ із типом доступу private
public: //розділ із типом доступу public
MyClass(){i=0;}//Конструктор. У описі відсутній тип результату.;
//Вхідні параметри відсутні. Це конструктор за замовчуванням;
MyClass(int a){i=a;}//Це також конструктор, але з параметром.
inline int get_i(){ return i; };
inline void set_i(int) { i=x; return; };
};
В даному прикладі два конструктори. Один по замовчуванню, який ініціалізує поле i класу MyClass нулем, та другий, який ініціалізує це поле заданим значенням. Тепер об’явити об’єкт даного класу можна у два способи за замовчуванням та із заданим значенням ініціалізації:
#include “MyClass.h”
…
MyClass MyObj1; //ініціалізація за замовчуванням
//поле i ініціалізується значенням 0.
MyClass MyObj1(1); //ініціалізація заданим значенням
//поле i ініціалізується значенням 1.
4. ДИНАМІЧНИЙ РОЗПОДІЛ ПАМ’ЯТІ
Для більш ефективного використання пам’яті часто доводиться розроблювати класи, в яких розмір об’єкту залежить від даних, що в ньому зберігаються. В таких структурах часто об’єм потрібної пам’яті стає відомим лише безпосередньо перед ініціалізацією конкретного об’єкта даного класу. Це призводить до необхідності динамічного керування пам’яттю. Для цих цілей в С++ передбачено два оператори new та delete. Оператор new дозволяє виділити пам’ять об’єкту, оператор delete дозволяє звільнити пам’ять Динамічний розподіл пам’яті вимагає використання покажчиків.
Розглянемо приклади.
Динамічне виділення пам’яті під одновимірний масив
float* y;
y=new float [5];
Очищення пам’яті, виділеної динамічно під одновимірний масив
delete y;
Динамічне виділення пам’яті під двовимірний масив
float** y;
y=new float* [5];
for(i=0;i<5;i++) {y[i]= new float[5] };
Очищення пам’яті, виділеної динамічно під двовимірний масив
for(i=0;i<5;i++) {delete y[i] };
delete y;
Зрозуміло, що оператор new використовується в конструкторі, а оператор delete в деструкторі. Розглянемо приклад.
Нехай нам потрібен клас одновимірний вектор, розмір якого визначається у момент ініціалізації. Такий клас повинен мати конструктор з параметром, що вказує на розмір вектора та конструктор за замовчуванням, щоб не виникали аварійні ситуації при ініціалізації без параметрів. Будемо вважати, що за замовчуванням наш вектор буде тривимірним. Щоб не ускладнювати приклад в описі класу покажемо лише конструктори та деструктори, а інші необхідні методи не показуватимемо.
class MyVector
{
private:
float *v;
int size;
public:
MyVector(){size=3; v= new float[size];}; //конструктор за замовчуванням
MyVector(int a) {size= a; v= new float[size];}; //конструктор з параметром
~MyVector(){delete[] v;};//деструктор
...
};
5. ЕЛЕМЕНТАРНІ МЕТОДИ СОРТУВАННЯ
В якості нашої першої екскурсії в область алгоритмів сортування, ми вивчимо деякі «елементарні» методи які добре працюють для невеликих файлів або файлів спеціальної структури. Існує кілька причин, за якими бажано вивчення цих простих методів. По-перше, вони дають нам відносно безболісний спосіб вивчити термінологію і основні механізми роботи алгоритмів сортування, що дозволяє отримати необхідну базу для вивчення більш складних алгоритмів. По-друге, для багатьох завдань сортування буває краще використовувати прості методи, чим більш складні алгоритми. І, нарешті, деякі з простих методів можна розширити до більш хороших методів або використовувати їх для поліпшення більш складних.
У деяких програмах сортування краще використовувати прості алгоритми. Програми сортування часто використовуються тільки один раз (або кілька разів). Якщо кількість елементів, які потрібно відсортувати не велика (скажімо менше ніж 500 елементів), то може статися, що використання простого алгоритму буде більш ефективно, ніж розробка та налагодження складного алгоритму. Елементарні методи завжди придатні для маленьких файлів (скажімо менших, ніж 50 елементів); малоймовірно, що складний алгоритм було б розумно використовувати для таких файлів, якщо звичайно не потрібно сортувати велика кількість таких файлів.
Як правило, елементарні методи, які ми будемо обговорювати, виробляють близько операцій для сортування N довільно взятих елементів. Якщо N досить мало, то це може і не бути проблемою, і якщо елементи розподілені не довільним чином, то ці алгоритми можуть працювати навіть швидше, ніж складні. Однак варто запам'ятати те, що ці алгоритми не слід використовувати для великих, довільно впорядкованих файлів, з одним єдиним виключенням для алгоритму оболонкової сортування, який часто використовується в багатьох програмах.
Перед тим, як розглядати будь-який конкретний алгоритм, було б корисно вивчити термінологію і деякі основні угоди про алгоритми сортування. Ми будемо вивчати алгоритми для сортування файлів записів містять ключі. Ключі, які є тільки частиною запису (часто дуже маленькою їх частиною), використовуються для управління процесом сортування. Метою алгоритму сортування є переорганизация записів у файлі так, щоб вони розташовувалися в ньому в деякому суворо визначеному порядку (зазвичай в алфавітному або числовому).
Якщо сортований файл цілком міститься в пам'ять (або цілком поміщається в масив), то для нього ми використовуємо внутрішні методи сортування. Сортування даних зі стрічки або диска називається зовнішньою сортуванням. Головна відмінність між ними полягає в тому, що при внутрішній сортування будь-який запис легко доступна, у той час як при зовнішній сортування ми можемо користуватися записами тільки послідовно, або великими блоками. Більшість алгоритмів сортування, які ми розглянемо - внутрішні.
Кількість використовуваної додаткової пам'яті алгоритму сортування - це ще один важливий фактор, який ми будемо брати до уваги. Взагалі кажучи, методи сортування діляться на три типи: методи сортування, які сортують без використання додаткової пам'яті, за винятком, можливо, невеликого стека і / або масиву; методи, які використовують для сортування зв'язані списки і тому використовують N додаткових покажчиків що зберігаються в пам'яті; і методи, які потребують додаткової пам'яті для зберігання копії сортованого файлу.
Стабільність - ще одна важлива характеристика методів сортування. Метод сортування називається стабільним, якщо він зберігає відносних порядок проходження записів з однаковими ключами. Наприклад, якщо алфавітний список групи сортується за оцінками, то стабільний метод створює список, в якому прізвища студентів з однаковими оцінками будуть упорядковані за абеткою, а нестабільний метод створить список в якому, можливо, вихідний порядок буде порушений. Більшість простих методів стабільні, у той час як більшість добре відомих складних методів - немає. Якщо стабільність необхідна, то вона може бути досягнута за допомогою додавання до ключа невеликого індексу перед сортуванням або за допомогою подовження, яким-небудь чином, ключа. Стабільність із легкістю приймається за норму; до нестабільності люди ставляться з недовірою. Насправді ж, лише деякі методи досягають стабільності без використання додаткового часу або місця.
Наступна програма, для сортування трьох записів, призначена для ілюстрації основних угод, які ми будемо використовувати. Зокрема, головна програма цікава тим, що вона працює тільки для N = 3; сенс у тому, що будь-яка програма сортування може бути зведена до процедури sort3 цієї програми.
Три оператора присвоєння, кожен з яких супроводжується оператором if, на ділі реалізують операцію «обміну». Ми вставляємо її безпосередньо в програмний код замість використання виклику процедури, оскільки вони є основою багатьох алгоритмів і часто потрапляють всередину циклу.
Щоб сконцентруватися на алгоритмічних питаннях, ми будемо працювати з алгоритмами, які просто сортують масиви цілих в чисельному порядку. Загалом, дуже легко адаптувати такі алгоритми для практичного використання, що включає в себе роботу з великими ключами або записами. В основному програми сортування працюють із записами двома способами: або вони порівнюють і сортують тільки ключі, або пересувають запису цілком. Більшість алгоритмів, які ми вивчимо можна застосовувати, за допомогою їх переформулювання в термінах цих двох операцій, для довільних записів. Якщо сортовані запису досить великі, то зазвичай намагаються уникнути пересування їх за допомогою «непрямої сортування»: при цьому самі записи не переупорядочіваются, а замість цього переупорядочівается масив покажчиків (індексів), так, що перший покажчик вказує на найменший елемент і так далі. Ключі можуть зберігатися або з записами (якщо вони великі), або з покажчиками (якщо вони маленькі). Якщо необхідно, то після сортування запису можна впорядкувати. Це описано далі.
Програма sort3 використовує навіть більш обмежений доступ до файлу: це три операції виду «порівняти два записи і обміняти їх, якщо потрібно, щоб помістити запис з меншим ключем на перше місце». Програми, обмежені такими операціями цікаві, оскільки вони підходять для реалізації на апаратному рівні. Ми вивчимо їх більш докладно пізніше.
Всі приклади програм використовують для сортування глобальний масив. Це не означає, що такий підхід краще або гірше ніж передача масиву як параметра. Все залежить від точки зору і конкретного алгоритму. Масив зроблений глобальним тільки тому, що тоді приклади стають коротшими і зрозуміліше.
5.1. Сортування вибором
Один з найпростіших методів сортування працює наступним чином: знаходимо найменший елемент в масиві і обмінюємо його з елементом знаходяться на першому місці. Потім повторюємо процес з другої позиції у файлі і знайдений елемент обмінюємо з другим елементному і так далі поки весь масив не буде відсортований. Цей метод називається сортування вибором, оскільки він працює, циклічно вибираючи найменший з елементів, що залишилися, як показано на малюнку 1. При першому проході символ пропуску йде на перше місце, обмінюючись з буквою 'П'. На другому проході елемент 'В' обмінюється з елементом 'Р' і так далі.
Наступна програма дає повну реалізацію цього процесу. Для кожного i від 1 до N-1, вона обмінює найменший елемент з a [i .. N] з a [i]:
У міру просування покажчика i зліва направо через файл, елементи ліворуч від вказівника знаходяться вже у своїй кінцевій позиції (і їх більше вже не будуть чіпати), тому масив стає повністю відсортованим до того моменту, коли покажчик досягає правого краю.
Цей метод - один з найпростіших, і він працює дуже добре для невеликих файлів. Його «внутрішній цикл» складається з порівняння a [i] <a [min] (плюс код необхідний для збільшення j та перевірки на те, що він не перевищив N), що навряд чи можна ще спростити.
Крім того, хоча сортування вибором є методом «грубої сили», він має дуже важливе застосування: оскільки кожен елемент пересувається не більше ніж раз, то він дуже гарний для великих записів з маленькими ключами.
5.2. Сортування вставкою
Метод сортування вставкою, майже настільки ж простий, що і сортування вибором, але набагато більш гнучкий. Цей метод часто використовують при сортуванні карток: беремо один елемент і вставляємо його в потрібне місце серед тих, що ми вже обробили (тим самим залишаючи їх отортірованнимі).
Розглянутий елемент вставляється в позицію за допомогою пересування більшого елемента на одну позицію вправо і за розміщенням меншого елемента в звільнилася позицію, як показано на малюнку 2. Так 'І' при третьому кроці менше всіх інших відсортованих елементів, тому ми «топимо» його в початок масиву. 'М »більше' І 'але менше за всіх інших, тому ми поміщаємо його між' І 'і' П ', і так далі.
Цей процес реалізований в наступній програмі. Для кожного i від 2 до N, подмассів a [1 .. i] сортується за допомогою приміщення a [i] у відповідну позицію серед уже відсортованих елементів:
Також як і при сортуванні вибором, в процесі сортування елементи ліворуч від вказівника i знаходяться вже в сортованого порядку, але вони не обов'язково знаходяться у своїй останній позиції, оскільки їх ще можуть пересунути направо щоб вставити більш маленькі елементи зустрінуті пізніше. Масив стає повністю сортований коли покажчик досягає правого краю.
Проте є ще одна важлива деталь: програма insertion не завжди працює, оскільки while може проскочити за лівий край масиву, коли v - найменший елемент масиву. Щоб виправити ситуацію, ми поміщаємо «сторожовий» ключ в a [0], роблячи його, по крайней мере, не більше, ніж найменший ключ масиву. Сторожові елементи повсюдно використовуються в ситуаціях подібних до цієї для запобігання додаткової перевірки (у даному випадку j> 0), що майже завжди допомагає у внутрішніх циклах.
5.3. Бульбашкове сортування
Елементарний метод сортування, який часто дають на вступних заняттях - це бульбашкова сортування: Завдання, що стоять поруч елементи масиву обмінюються місцями, до тих пір, поки зустрічаються невідсортовані пари. Реалізація цього методу дана нижче.
Щоб повірити в те, що вона насправді працює, може знадобитися якийсь час. Для цього зауважте, що коли під час першого проходу ми зустрічаємо максимальний елемент, ми обмінюємо його з кожним елементом праворуч від нього поки він не опиниться в крайній правій позиції. На другому проході ми поміщаємо другий максимальний елемент у передостанню позицію і так далі. Бульбашкова сортування працює також як і сортування вибором, хоча вона і робить набагато більше роботи на те, щоб перемістити елемент у його кінцеву позицію.
5.4. Характеристики найпростіших сортувань
Властивість 1 Сортування вибором використовує близько N обмінів.
Властивість 2 Сортування вставкою використовує в два рази більше в найгіршому випадку.
Властивість 4 Сортування вставкою лінійна для «майже сортованих» файлів.
Властивість 5 Сортування вибором лінійна для файлів з великими записами і маленькими ключами.
5.5. Сортування файлів з великими записами
Дуже часто буває можливо (і бажано) зробити так, щоб під час сортування файлу складається з N елементів будь-якому методом було б зроблено тільки N операцій обміну повного запису за допомогою непрямої адресації до елементів масиву (використовуючи масив індексів або покажчиків), а саму реорганізацію робити після.
Більш конкретно: якщо масив a [1 .. N] містить великі запису, то ми віддамо перевагу використовувати масив покажчиків p [1 .. N] для того, щоб знати, де знаходиться черговий елемент масиву a, і для твору псевдообмена. Нижче наведена програма сортування вставкою з використанням масиву покажчиків:
Для запобігання зайвого контролю в циклі, у програмі знову використовуються «сторожові» елементи.
Спочатку, індекси йдуть по порядку. Потім порядок індексів починає змінюватися так, щоб масив a, прочитаний по порядку читання індексів був упорядкований.
Для цього ми можемо використовувати наступну процедуру, яка фізично впорядковує запису файлу використовуючи при цьому N перестановок:
5.6. Сортування Шелла
Сортування вставкою працює повільно тому, що вона обмінює тільки суміжні елементи. Оболочечная сортування є найпростішим розширенням сортування вставкою, яка збільшує швидкість роботи алгоритму за рахунок того, що дозволяє обмінювати елементи, що знаходяться далеко один від одного.
Основна ідея алгоритму полягає в тому, щоб відсортувати всі групи файлу складаються з елементів файлу віддалених один від одного на відстань h. Такі файли називаються h-сортований. Коли ми h-сортуємо файл по деякому великим h, ми пересуваємо його елементи на великі відстані. Це полегшує роботу сортування для менших значень h. Процес закінчується коли h зменшується до 1.
6. ПРАКТИЧНА РЕАЛІЗАЦІЯ ПРОСТИХ МЕТОДІВ СОРТУВАННЯ
1. Написати програму, що реалізує один з простих методів сортування: пpоцедуpи соpтування методами Шелла, пірамідального та швидкого соpтування мiстяться у файлах.
2. Згенерувати три масиви з випадковими елементами типу Integer довжиною 100, 1000 та 10000 елементів, відповідно.
3. Відсортувати одержані масиви за збільшенням елементів, визначивши при цьому такі параметри:
кількість порівнянь;
кількість обмінів;
фактичний час роботи,
необхідні кожній з програм (простий та один з довершених методів), щоби відсортувати кожен з трьох масивів. Швидкодія сучасних ЕОМ може привести до того, що час роботи процедури буде дорівнювати нулеві з точністю, яку забезпечує системний таймер. Тоді варто запустити її багато разів у циклі, а потім усереднити результат.
Текст програми
#include <stdlib.h> // div_t rand
#include <conio.h> // clrscr()
#include <math.h>
#include <iostream> // cin, cout
#include <fstream> // ofstream
#include <time.h>
using namespace std;
const long int
N=1000, // Array dimension
M=int(log((double)N)/log((double)2)+1); // Parameter for ShellSort. Never change it !
unsigned long moves, compares;
struct tItem {
int key;
char data[4];
friend bool operator < (tItem x, tItem y) { return (x.key < y.key); }
friend bool operator <= (tItem x, tItem y) { return (x.key <= y.key);}
friend bool operator > (tItem x, tItem y) { return (x.key > y.key); }
friend bool operator >= (tItem x, tItem y) { return (x.key >= y.key);}
friend void swap(tItem& a, tItem& b);
friend void copy(tItem& a, tItem& b);
tItem& operator = (tItem& y) { copy(*this, y); return *this; };
};
void swap(tItem& x, tItem& y) {
int k = x.key; x.key = y.key; y.key = k;
char s[4];
strcpy(s, x.data); strcpy(x.data, y.data); strcpy(y.data, s);
};
void copy(tItem& x, tItem& y) {
x.key = y.key;
strcpy(x.data, y.data);
};
ofstream fout("sort.txt");
void print(char * text, tItem * a, int N, bool sorted) {
fout << endl << text;
if (N<101 && !sorted) {
fout << endl;
for(int i=0;i<N;i++) {
fout << a[i].key << " " << a[i].data << " ";
if ((i+1)%10==0) fout << endl;
}
}
if (sorted)
for(int i=0;i<N;i++) {
if (i>0 && a[i-1] > a[i]) {
fout << a[i-1].key << "(" << a[i-1].data << ") > " << a[i].key << "(" << a[i].data << ") ! " << endl;
}
}
}
//++++++++++++++++Quicksort++++++++++++++++++++++++++++++++++
void QuickSort(tItem * a, int L, int R) {
int m,i,j;
tItem x;
i = L;
j = R;
m=(L+R)/2;
x = a[m];
while (i<=j) {
while (a[i]<x) { i++; }
while (x<a[j]) { j--; }
if (i<=j) {
if (i<j) {
swap(a[i], a[j]);
//c
21.11.2013 11:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора