Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Прості методи сортування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Програмування частина 4 Технологія системного програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Інститут дистанційного навчання
Кафедра СКС
КУРСОВА РОБОТА
з дисципліни «Програмування»
на тему «Прості методи сортування»
Варіант № 21
Завдання на курсову роботу:
1. Провести огляд методів сортування масивів, що широко застосовуються у програмуванні. Розглянути їх властивості і практичне значення.
2. Провести детальний аналіз літератури та Інтернет джерел щодо динамічного розподілу пам’яті: робота з пам’яттю, функція для динамічного виділення пам’яті malloc(), функція динамічного виділення пам’яті calloc(), розширення динамічної області пам’яті за допомогою функції realloc(), звільнення пам’яті з допомогою функції free().
3. Написати програму, що реалізує один з простих методів сортування: пpоцедуpи соpтування методами Шелла, пірамідального та швидкого соpтування мiстяться у файлах.
4. Згенерувати три масиви з випадковими елементами типу Integer довжиною 100, 1000 та 10000 елементів, відповідно.
5. Відсортувати одержані масиви за збільшенням елементів, визначивши при цьому такі параметри:
кількість порівнянь;
кількість обмінів;
фактичний час роботи,
необхідні кожній з програм (простий та один з довершених методів), щоби відсортувати кожен з трьох масивів.
ЗМІСТ
ВСТУП……………………………………………………………………….
4
1.
СТАТИЧНІ ТА ДИНАМІЧНІ МАСИВИ………………………….
6
1.1
Методи сортування масивів…………………………………………….
6
1.2
Сортування за допомогою включення…………………………………
7
2.
ДИНАМІЧНИЙ РОЗПОДІЛ ПАМ’ЯТІ…………………………….
9
2.1
Робота з пам’яттю……………………………………………………….
9
2.2
Функція для динамічного виділення пам’яті malloc()………………...
10
2.3
Функція динамічного виділення пам’яті calloc()……………………..
11
2.4
Розширення динамічної області пам’яті за допомогою функції realloc()…………………………………………………………………..
11
2.5
Приклад використання функції для перерозподілу пам’яті…………..
12
2.6
Звільнення пам’яті з допомогою функції free()……………………….
13
3.
ЕЛЕМЕНТАРНІ МЕТОДИ СОРТУВАННЯ………………………..
14
3.1
Сортування вибором…………………………………………………….
18
3.2
Сортування вставкою……………………………………………………
18
3.3
Бульбашкове сортування……………………………………………….
19
3.4
Характеристики найпростіших сортувань…………………………….
19
3.5
Сортування файлів з великими записами……………………………...
19
3.6
Сортування Шелла………………………………………………………
20
4.
ПРАКТИЧНА РЕАЛІЗАЦІЯ ПРОСТИХ МЕТОДІВ СОРТУВАННЯ…………………………………………………………
21
ВИСНОВКИ…………………………………………………………………..
28
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ……………………………..
29
ВСТУП
Мова С++ багато в чому є надмножиною Сі. Нові можливості С++ включають оголошення у вигляді виразів, перетворення типів у вигляді функцій, оператори new і delete, тип bool, посилання, розширене поняття константної, підставлювані функції, аргументи за умовчанням, перевизначення, простори імен, класи (включаючи і всі пов'язані з класами можливості, такі як спадкоємство, члени функцій, віртуальні функції, абстрактні класи і конструктори), перевизначення операторів, шаблони, оператор, обробку виключень, динамічну ідентифікацію і багато що інше. Мова Си++ також у багатьох випадках строго відноситься до перевірки типів, ніж Сі.
У С++ з'явилися коментарі у вигляді подвійною косою риси («//»), які були в попереднику Сі — мові BCPL.
Деякі особливості С++ пізніше були перенесені в Сі, наприклад ключові слова const і inline, оголошення в циклах for і коментарі в стилі Си++ («//»). У пізніших реалізаціях Сі також були представлені можливості, яких немає в С++, наприклад макроси vararg і поліпшена робота з параметрами масивів.
C++ надзвичайно могутня мова, що містить засоби створення ефективних програм практично будь-якого призначення, від низькорівневих утиліт і драйверів до складних програмних комплексів самого різного призначення. Зокрема:
Висока сумісність з мовою С, що дозволяє використовувати весь існує С-код (код З може бути з мінімальними переробками скомпільований компілятором С++; бібліотеки, написані, звичайно можуть бути викликані з С++ безпосередньо без яких-небудь додаткових витрат, у тому числі і на рівні функцій зворотного виклику, дозволяючи бібліотекам, написаним, викликати код, написаний на С++).
Підтримуються різні стилі і технології програмування, включаючи традиційне директивне програмування, ООП, узагальнене програмування, метапрограмування (шаблони, макроси). Є можливість роботи на низькому рівні з пам'яттю, адресами, портами. Можливість створення узагальнених контейнерів і алгоритмів для різних типів даних, їх спеціалізація і обчислення на етапі компіляції, використовуючи шаблони.
Доступні компілятори для великої кількості платформ, на мові C++ розробляють програми для самих різних платформ і систем. Мова спроектована так, щоб дати програмісту максимальний контроль над всіма аспектами структури і порядку виконання програми. Жодна з мовних можливостей, що приводить до додаткових накладних витрат, не є обов'язковою для використання — при необхідності мова дозволяє забезпечити максимальну ефективність програми.
1. СТАТИЧНІ ТА ДИНАМІЧНІ МАСИВИ
Масив – це набір однотипних елементів. Кожен елемент має свій номер (індекс). Всі елементи масиву упорядковані за своїм індексом. Масив може бути одновимірним чи багатовимірним. Елементи масиву можуть мати просту чи складну структуру в залежності від функціонального призначення даного масиву. Основною особливістю масивів є те, що на етапі виділення пам’яті для збереження елементів масиву відома точна кількість елементів масиву.
Основними операціями при роботі з масивами є:
- виділення пам’яті для збереження елементів масиву;
- вивільнення пам’яті;
- сортування елементів масиву;
- пошук елемента масиву, що відповідає заданому критерію пошуку.
Виділення пам’яті під масив може бути статичним, коли кількість елементів масиву відома на етапі розробки програми, або динамічним, коли кількість елементів масиву стає відомою під час виконання програми. При статичному виділенні вивільнення пам’яті відбувається автоматично при закінченні роботи програми і програміст не має змоги виконати вивільнення пам’яті під час роботи програми. При динамічному виділенні вивільнення пам’яті також відбувається автоматично при закінченні роботи програми, але програміст може при необхідності вивільнити пам’ять в процесі виконання програми. Це робить програми більш гнучкими, тому в сучасному програмуванні все частіше використовують динамічне виділення пам’яті при роботі з масивами.
1.1. Методи сортування масивів
При роботі з масивами найчастіше доводиться виконувати операції сортування та пошуку даних. Від ефективності реалізації цих операцій часто залежить ефективність всієї програми, тому розглянемо ці операції детальніше.
Сортування – це процес перегрупування даних у деякому заданому порядку. Основна мета сортування – полегшити пошук потрібної інформації у заданій послідовності даних.
Методи сортування поділяються на внутрішні (дані розміщуються в оперативній пам'яті) та зовнішні (дані розміщуються в файлах). Для внутрішнього сортування використовуються методи сортування за допомогою включення, за допомогою вибору, за допомогою обміну і т.д.
Розглянемо вказані внутрішні методи. Для визначеності будемо вважати, що необхідно виконати сортування у порядку зростання елементів масиву, і всі приклади, що будуть розглянуті відповідатимуть саме такому порядку сортування. Читачеві ж рекомендуємо для тренування модифікувати наведені програми для сортування у зворотному напрямку.
1.2. Сортування за допомогою включення
При сортуванні за допомогою включення елементи умовно ділять на вже відсортовану послідовність a1…ai-1 і вихідну послідовність ai…an. На кожному кроці починаючи з i=2 та збільшуючи кожен раз i на одиницю, із вихідної (початкової) послідовності видобувається i-тий елемент і перекладається в уже готову послідовність. При цьому він вставляється в потрібне місце готової послідовності. В процесі пошуку потрібного місця чергуються операція порівняння даного елемента з елементами послідовності та операція переміщення по послідовності, тобто вибраний елемент порівнюється з черговим елементом aj , а тоді ai або вставляється на місце елемента aj (якщо виконано критерій сортування), тоді відповідно aj зміщується на одну позицію вправо або ai порівнюється з наступним елементом aj-1 (якщо критерій сортування не виконано), при цьому aj знову ж таки зміщується на одну позицію вправо. Нижче наведено приклад сортування методом включення масиву цілих чисел . Для демонстрації на екран виводяться вихідний масив та результуючий масив.
Приклад:
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
//Шаблон функції сортування елементів масиву методом включення
template <class T> void vstavka(T* massive,int size);
void main()
{
//Оголошення змінних, необхідних для реалізації алгоритму
int* mas;
int n,i;
//Очищення екрану
clrscr();
//Запит на введення розміру масиву
cout << "Input n" << endl;
cout << "n=";
cin >> n;
cout << "creating massive of random numbers:"<<endl;
//Динамічне виділення пам’яті під елементи масиву
mas=new int[n];
//Підключення генератору випадкових чисел
randomize();
//Формування масиву випадкових чисел
for (i=0;i<n;i++)
{
//Формування елементу масиву випадковим чином
mas[i]=random(100)-50;
//Відображення на екрані сформованого елементу
cout << mas[i]<<" ";
}
//Переведення курсору на наступну строку екрану
cout << endl;
//Сортування елементів масиву методом включення
vstavka(mas, n);//Відображення на екрані відсортованого масиву
cout << "massiv after sorting:" << endl;
for(i=0;i<n;i++)
{
cout << mas[i] << " ";
}
//Очищення пам’яті, виділеної під масив
delete mas;
return;
35
}
//Реалізація шаблону функції сортування елементів масиву методом
//включення опис алгоритму див вище
template <class T> void vstavka(T* massive,int size)
{
T tmp;
int i,j;
for(i=1;i<size;i++)
{
tmp=massive[i];
j=i;
while(tmp<massive[j-1])
{
massive[j]=massive[j-1];
j--;
if(j==0) break;
}
massive[j]=tmp;
}
return;
}
2. ДИНАМІЧНИЙ РОЗПОДІЛ ПАМ’ЯТІ
2.1. Робота з пам’яттю
Усі змінні, оголошені в програмі розташовуються в одній безперервній області пам'яті, що називають сегментом даних. Такі змінні не змінюють свого розміру в ході виконання програми й називаються статичними. Розміру сегмента даних може бути недостатньо для розміщення великих масивів інформації. Виходом із цієї ситуації є використання динамічної пам’яті.
Динамічна пам’ять - це пам’ять, що виділяється програмі для її роботи за винятком сегмента даних, стека, у якому розташовуються локальні змінні підпрограм і самі тексти програм.
Для роботи з динамічною пам’яттю використовуються вказівники. З їхньою допомогою здійснюється доступ до ділянок динамічної пам'яті, які називаються динамічними змінними. Динамічні змінні створюються за допомогою спеціальних функцій й операцій. Вони існують або до кінця роботи програм, або доти, поки не будуть знищені за допомогою спеціальних функцій або операцій.
Бібліотека містить функції для розподілу пам’яті в процесі виконання програми. Цей процес називається динамічним розподілом пам’яті. До тепер ми розглядали статичний розподіл пам’яті, при якому треба знати об’єм пам’яті до написання програми. Динамічний розподіл дозволяє оперативно запрошувати пам’ять в процесі виконання програми. Статичні дані і текст програм займають певний об’єм пам’яті. Решту об’єму пам’яті можна розподіляти динамічно. Якщо велика програма працює в системі з невеликим об’ємом оперативної пам’яті, то для динамічних операцій залишається мало пам’яті.
Наявність вільної пам’яті і її розподіл залежить від операційної системи, але це не справа програміста. Операційна система або виділяє ділянку пам’яті, або ні, механізми залишаються за кадром.
2.2. Функція для динамічного виділення пам’яті malloc()
Прототип функції
void *malloc(unsigned s) — повертає вказівник на початок області динамічної пам’яті довжиною s байт. Якщо потрібний об’єм пам’яті функція не може виділити, то вона повертає NULL, або аргумент її =0, тобто s=0.
Приклад:
int *u;
u=(int*)malloc(sizeof(int)); // у функцію передається кількість необхідної пам'яті в байтах. Оскільки функція повертає значення типу void*, то його необхідно перетворити до типу вказівника (int*).
Приклад виділення пам’яті функцією malloc().
#include <stdio.h>
#include <stdlib.h>
int k, m, int *ptr1;
void main() { /*Виділяється 4*k байт пам(яті, одержуємо адресу виділеного блоку */
for (k=1; k<=6; k=k+1) {ptr1= malloc(4*k);
m=(ptr1+k-1); Додається розмір, кратний байтам
printf("k=%d %d %d\n", k, ptr1, m+3); }
2.3. Функція динамічного виділення пам’яті calloc()
Прототип функції
Void *calloc(unsigned n, unsigned m) - повертає вказівник на початок області динамічної пам’яті для розміщення n елементів довжиною m байт кожний. Якщо потрібний об’єм пам’яті функція не може виділити, то вона повертає NULL, або аргументи її =0, тобто n =0 або m=0.
Приклад програми використання функції calloc():
#include <stdio.h>
#include <stdlib.h>
int k, m, int *ptr1;
void main() / Виділяється 4*16 байт пам(яті, одержуємо адресу виділеного блоку */
ptr1= calloc(4,16);
printf("%d %d \n", current, current+1 );} Початок кінець
Результат 40240672 40240676
2.4. Розширення динамічної області пам’яті за допомогою функції realloc()
Прототип функції
void *realloc (void *p, unsigned s)
Функція змінює розмір блоку раніше виділеної динамічної пам’яті до розміру s байт, р - адреса початку змінюваного блоку, при невдалому завершенні повертає NULL;
Аргумент ptr вказує на нововиділений блок пам’яті. Новий розмір в байтах вказується параметром s. При виклику realloc() можливі такі випадки.
Якщо для розширення блоку, який знаходиться за адресою ptr є достатня кількість пам’яті, то вона виконується і функція повертає ptr.
Якщо пам’яті не досить, щоб розширити існуючий блок по його текучій адресі, то створюється новий блок потрібного розміру s і дані копіюються з старого блоку в початок нового. Старий блок звільняється і функція повертає вказівник на новий блок пам’яті.
Якщо аргумент = NULL, то функція діє так як і malloc(), виділяючи блок пам’яті розміром s байт і повертаючи вказівник на нього.
Якщо аргумент size=0, блок пам’яті по адресі ptr звільняється і функція повертає NULL.
Якщо для перерозподілу недосить пам’яті (тобто не можна ні розширити старий блок, ні розмістити новий), функція повертає NULL, а початковий блок стає незмінним.
2.5. Приклад використання функції для перерозподілу пам’яті
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void main( ){
char buf[30]="qwertyyuiioopoppppppppppppp", *message;
/* Розміщення блоку і копіювання рядка в нього */
message = realloc(NULL, strlen(buf)+1);
strcpy(message, buf);
puts(message); /* Вивід вмістимого по адресі message*/
/* Розширення блоку і приєднання до нього даного рядка */
message = realloc(message,(strlen(message) + strlen(buf)+1));
strcat(message, buf);
/* Вивід повідомлення*/
puts(message); }
Результат:
qwertyyuiioopoppppppppppppp
qwertyyuiioopopppppppppppppqwertyyuiioopoppppppppppppp
2.6. Звільнення пам’яті з допомогою функції free()
Пам’ять розподіляється з динамічної області. При розподілу пам(яті за допомогою функцій malloc() і calloc() ця пам(ять береться з динамічної області, яка доступна програмі. Але вона має межі. Коли програма закінчила роботу з блоком динамічно виділеної пам’яті, її треба звільнити. Звільнену пам’ять можна далі динамічно розподіляти. Для звільнення динамічно розподіленої пам’яті використовується функція free().
Прототип функції:
void free(void *ptr);
Функція звільняє раніше виділену ділянку динамічної пам'яті, на яку вказує адреса р. Цей блок повинен бути раніше виділений однією з функцій malloc(), realloc() і calloc(). Якщо вказівник рівний NULL функція нічого не дає. Приклад звільнення динамічного розподілу пам’яті.
#include <stdio.h>
#include <stdlib.h>
int k, m, int *ptr1;
void main() { /*Виділяється 4*k байт пам(яті, одержуємо адресу виділеного блоку */
for (k=1; k<=6; k=k+1) {ptr1= malloc(4*k);
m=(ptr1+k-1); Додається розмір, кратний байтам
printf("k=%d %d %d\n", k, ptr1, m+3);
free(ptr1); /* Звільнення блоку пам(яті по адресу ptr1*/ }
3. ЕЛЕМЕНТАРНІ МЕТОДИ СОРТУВАННЯ
В якості нашої першої екскурсії в область алгоритмів сортування, ми вивчимо деякі «елементарні» методи які добре працюють для невеликих файлів або файлів спеціальної структури. Існує кілька причин, за якими бажано вивчення цих простих методів. По-перше, вони дають нам відносно безболісний спосіб вивчити термінологію і основні механізми роботи алгоритмів сортування, що дозволяє отримати необхідну базу для вивчення більш складних алгоритмів. По-друге, для багатьох завдань сортування буває краще використовувати прості методи, чим більш складні алгоритми. І, нарешті, деякі з простих методів можна розширити до більш хороших методів або використовувати їх для поліпшення більш складних.
У деяких програмах сортування краще використовувати прості алгоритми. Програми сортування часто використовуються тільки один раз (або кілька разів). Якщо кількість елементів, які потрібно відсортувати не велика (скажімо менше ніж 500 елементів), то може статися, що використання простого алгоритму буде більш ефективно, ніж розробка та налагодження складного алгоритму. Елементарні методи завжди придатні для маленьких файлів (скажімо менших, ніж 50 елементів); малоймовірно, що складний алгоритм було б розумно використовувати для таких файлів, якщо звичайно не потрібно сортувати велика кількість таких файлів.
Як правило, елементарні методи, які ми будемо обговорювати, виробляють близько операцій для сортування N довільно взятих елементів. Якщо N досить мало, то це може і не бути проблемою, і якщо елементи розподілені не довільним чином, то ці алгоритми можуть працювати навіть швидше, ніж складні. Однак варто запам'ятати те, що ці алгоритми не слід використовувати для великих, довільно впорядкованих файлів, з одним єдиним виключенням для алгоритму оболонкової сортування, який часто використовується в багатьох програмах.
Перед тим, як розглядати будь-який конкретний алгоритм, було б корисно вивчити термінологію і деякі основні угоди про алгоритми сортування. Ми будемо вивчати алгоритми для сортування файлів записів містять ключі. Ключі, які є тільки частиною запису (часто дуже маленькою їх частиною), використовуються для управління процесом сортування. Метою алгоритму сортування є переорганизация записів у файлі так, щоб вони розташовувалися в ньому в деякому суворо визначеному порядку (зазвичай в алфавітному або числовому).
Якщо сортований файл цілком міститься в пам'ять (або цілком поміщається в масив), то для нього ми використовуємо внутрішні методи сортування. Сортування даних зі стрічки або диска називається зовнішньою сортуванням. Головна відмінність між ними полягає в тому, що при внутрішній сортування будь-який запис легко доступна, у той час як при зовнішній сортування ми можемо користуватися записами тільки послідовно, або великими блоками. Більшість алгоритмів сортування, які ми розглянемо - внутрішні.
Кількість використовуваної додаткової пам'яті алгоритму сортування - це ще один важливий фактор, який ми будемо брати до уваги. Взагалі кажучи, методи сортування діляться на три типи: методи сортування, які сортують без використання додаткової пам'яті, за винятком, можливо, невеликого стека і / або масиву; методи, які використовують для сортування зв'язані списки і тому використовують N додаткових покажчиків що зберігаються в пам'яті; і методи, які потребують додаткової пам'яті для зберігання копії сортованого файлу.
Стабільність - ще одна важлива характеристика методів сортування. Метод сортування називається стабільним, якщо він зберігає відносних порядок проходження записів з однаковими ключами. Наприклад, якщо алфавітний список групи сортується за оцінками, то стабільний метод створює список, в якому прізвища студентів з однаковими оцінками будуть упорядковані за абеткою, а нестабільний метод створить список в якому, можливо, вихідний порядок буде порушений. Більшість простих методів стабільні, у той час як більшість добре відомих складних методів - немає. Якщо стабільність необхідна, то вона може бути досягнута за допомогою додавання до ключа невеликого індексу перед сортуванням або за допомогою подовження, яким-небудь чином, ключа. Стабільність із легкістю приймається за норму; до нестабільності люди ставляться з недовірою. Насправді ж, лише деякі методи досягають стабільності без використання додаткового часу або місця.
Наступна програма, для сортування трьох записів, призначена для ілюстрації основних угод, які ми будемо використовувати. Зокрема, головна програма цікава тим, що вона працює тільки для N = 3; сенс у тому, що будь-яка програма сортування може бути зведена до процедури sort3 цієї програми.
Три оператора присвоєння, кожен з яких супроводжується оператором if, на ділі реалізують операцію «обміну». Ми вставляємо її безпосередньо в програмний код замість використання виклику процедури, оскільки вони є основою багатьох алгоритмів і часто потрапляють всередину циклу.
Щоб сконцентруватися на алгоритмічних питаннях, ми будемо працювати з алгоритмами, які просто сортують масиви цілих в чисельному порядку. Загалом, дуже легко адаптувати такі алгоритми для практичного використання, що включає в себе роботу з великими ключами або записами. В основному програми сортування працюють із записами двома способами: або вони порівнюють і сортують тільки ключі, або пересувають запису цілком. Більшість алгоритмів, які ми вивчимо можна застосовувати, за допомогою їх переформулювання в термінах цих двох операцій, для довільних записів. Якщо сортовані запису досить великі, то зазвичай намагаються уникнути пересування їх за допомогою «непрямої сортування»: при цьому самі записи не переупорядочіваются, а замість цього переупорядочівается масив покажчиків (індексів), так, що перший покажчик вказує на найменший елемент і так далі. Ключі можуть зберігатися або з записами (якщо вони великі), або з покажчиками (якщо вони маленькі). Якщо необхідно, то після сортування запису можна впорядкувати. Це описано далі.
Програма sort3 використовує навіть більш обмежений доступ до файлу: це три операції виду «порівняти два записи і обміняти їх, якщо потрібно, щоб помістити запис з меншим ключем на перше місце». Програми, обмежені такими операціями цікаві, оскільки вони підходять для реалізації на апаратному рівні. Ми вивчимо їх більш докладно пізніше.
Всі приклади програм використовують для сортування глобальний масив. Це не означає, що такий підхід краще або гірше ніж передача масиву як параметра. Все залежить від точки зору і конкретного алгоритму. Масив зроблений глобальним тільки тому, що тоді приклади стають коротшими і зрозуміліше.
3.1. Сортування вибором
Один з найпростіших методів сортування працює наступним чином: знаходимо найменший елемент в масиві і обмінюємо його з елементом знаходяться на першому місці. Потім повторюємо процес з другої позиції у файлі і знайдений елемент обмінюємо з другим елементному і так далі поки весь масив не буде відсортований. Цей метод називається сортування вибором, оскільки він працює, циклічно вибираючи найменший з елементів, що залишилися, як показано на малюнку 1. При першому проході символ пропуску йде на перше місце, обмінюючись з буквою 'П'. На другому проході елемент 'В' обмінюється з елементом 'Р' і так далі.
Наступна програма дає повну реалізацію цього процесу. Для кожного i від 1 до N-1, вона обмінює найменший елемент з a [i .. N] з a [i]:
У міру просування покажчика i зліва направо через файл, елементи ліворуч від вказівника знаходяться вже у своїй кінцевій позиції (і їх більше вже не будуть чіпати), тому масив стає повністю відсортованим до того моменту, коли покажчик досягає правого краю.
Цей метод - один з найпростіших, і він працює дуже добре для невеликих файлів. Його «внутрішній цикл» складається з порівняння a [i] <a [min] (плюс код необхідний для збільшення j та перевірки на те, що він не перевищив N), що навряд чи можна ще спростити.
Крім того, хоча сортування вибором є методом «грубої сили», він має дуже важливе застосування: оскільки кожен елемент пересувається не більше ніж раз, то він дуже гарний для великих записів з маленькими ключами.
3.2. Сортування вставкою
Метод сортування вставкою, майже настільки ж простий, що і сортування вибором, але набагато більш гнучкий. Цей метод часто використовують при сортуванні карток: беремо один елемент і вставляємо його в потрібне місце серед тих, що ми вже обробили (тим самим залишаючи їх отортірованнимі).
Розглянутий елемент вставляється в позицію за допомогою пересування більшого елемента на одну позицію вправо і за розміщенням меншого елемента в звільнилася позицію, як показано на малюнку 2. Так 'І' при третьому кроці менше всіх інших відсортованих елементів, тому ми «топимо» його в початок масиву. 'М »більше' І 'але менше за всіх інших, тому ми поміщаємо його між' І 'і' П ', і так далі.
Цей процес реалізований в наступній програмі. Для кожного i від 2 до N, подмассів a [1 .. i] сортується за допомогою приміщення a [i] у відповідну позицію серед уже відсортованих елементів:
Також як і при сортуванні вибором, в процесі сортування елементи ліворуч від вказівника i знаходяться вже в сортованого порядку, але вони не обов'язково знаходяться у своїй останній позиції, оскільки їх ще можуть пересунути направо щоб вставити більш маленькі елементи зустрінуті пізніше. Масив стає повністю сортований коли покажчик досягає правого краю.
Проте є ще одна важлива деталь: програма insertion не завжди працює, оскільки while може проскочити за лівий край масиву, коли v - найменший елемент масиву. Щоб виправити ситуацію, ми поміщаємо «сторожовий» ключ в a [0], роблячи його, по крайней мере, не більше, ніж найменший ключ масиву. Сторожові елементи повсюдно використовуються в ситуаціях подібних до цієї для запобігання додаткової перевірки (у даному випадку j> 0), що майже завжди допомагає у внутрішніх циклах.
3.3. Бульбашкове сортування
Елементарний метод сортування, який часто дають на вступних заняттях - це бульбашкова сортування: Завдання, що стоять поруч елементи масиву обмінюються місцями, до тих пір, поки зустрічаються невідсортовані пари. Реалізація цього методу дана нижче.
Щоб повірити в те, що вона насправді працює, може знадобитися якийсь час. Для цього зауважте, що коли під час першого проходу ми зустрічаємо максимальний елемент, ми обмінюємо його з кожним елементом праворуч від нього поки він не опиниться в крайній правій позиції. На другому проході ми поміщаємо другий максимальний елемент у передостанню позицію і так далі. Бульбашкова сортування працює також як і сортування вибором, хоча вона і робить набагато більше роботи на те, щоб перемістити елемент у його кінцеву позицію.
3.4. Характеристики найпростіших сортувань
Властивість 1 Сортування вибором використовує близько N обмінів.
Властивість 2 Сортування вставкою використовує в два рази більше в найгіршому випадку.
Властивість 4 Сортування вставкою лінійна для «майже сортованих» файлів.
Властивість 5 Сортування вибором лінійна для файлів з великими записами і маленькими ключами.
3.5. Сортування файлів з великими записами
Дуже часто буває можливо (і бажано) зробити так, щоб під час сортування файлу складається з N елементів будь-якому методом було б зроблено тільки N операцій обміну повного запису за допомогою непрямої адресації до елементів масиву (використовуючи масив індексів або покажчиків), а саму реорганізацію робити після.
Більш конкретно: якщо масив a [1 .. N] містить великі запису, то ми віддамо перевагу використовувати масив покажчиків p [1 .. N] для того, щоб знати, де знаходиться черговий елемент масиву a, і для твору псевдообмена. Нижче наведена програма сортування вставкою з використанням масиву покажчиків:
Для запобігання зайвого контролю в циклі, у програмі знову використовуються «сторожові» елементи.
Спочатку, індекси йдуть по порядку. Потім порядок індексів починає змінюватися так, щоб масив a, прочитаний по порядку читання індексів був упорядкований.
Для цього ми можемо використовувати наступну процедуру, яка фізично впорядковує запису файлу використовуючи при цьому N перестановок:
3.6. Сортування Шелла
Сортування вставкою працює повільно тому, що вона обмінює тільки суміжні елементи. Оболочечная сортування є найпростішим розширенням сортування вставкою, яка збільшує швидкість роботи алгоритму за рахунок того, що дозволяє обмінювати елементи, що знаходяться далеко один від одного.
Основна ідея алгоритму полягає в тому, щоб відсортувати всі групи файлу складаються з елементів файлу віддалених один від одного на відстань h. Такі файли називаються h-сортований. Коли ми h-сортуємо файл по деякому великим h, ми пересуваємо його елементи на великі відстані. Це полегшує роботу сортування для менших значень h. Процес закінчується коли h зменшується до 1.
4. ПРАКТИЧНА РЕАЛІЗАЦІЯ ПРОСТИХ МЕТОДІВ СОРТУВАННЯ
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 = a[i];
//a[i] = a[j];
//a[j] = c;
}
i++; j--;
}
}
if (L<j) {QuickSort(a,L,j);}
if (i<R) {QuickSort(a,i,R);}
}
//++++++++++++++++ShellSort++++++++++++++++++++++++++++++++++
void ShellSort(tItem *
21.11.2013 11:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора