Міністерство освіти і науки Російської Федерації
федеральне державне бюджетне освітня установа вищої професійної освіти
Московський державний університет друку імені Івана Федорова
Інститут прінтмедіа та інформаційних технологій
Кафедра інформатики та інформаційних технологій
Реферат на тему:
Алгоритми сортування
Виконала студентка
Котенєва Алена Валериевна
Перевірив доц. Іванько М.А.
Москва +2014
Зміст
Введення
Метод бульбашки
Сортування вибором
Сортування вибором в блок-схемі
Сортування вставками
Метод Шелла
Швидке сортування
Висновок
Список використаної літератури
Введення
Алгоритми сортування обробляють масиви елементів будь-якого типу. Таке завдання увазі упорядкування елементів масиву в певному порядку. Зазвичай по зростанню і спаданню даних. Впорядкувати набір даних означає переставити елементи в певному порядку так, щоб йшло зростання або убування з кожним кроком.
Видатні алгоритми сортування даних, розташованих в оперативній пам'яті, надзвичайно різноманітні. Їх аналіз дуже корисний з погляду навчання, оскільки в них використовуються практично всі універсальні прийоми конструювання алгоритмів будь-якої складності.
Алгоритм сортування - це алгоритм, який допомагає впорядкувати набір даних в таблиці в певну послідовність. Зазвичай, масиви сортують за зменшенням і зростанню.
У зв'язку з різноманітністю завдань на сортування даних таблиць, існує багато різних метод сортування, які доцільно використовувати в різних ситуаціях, з метою економії коштів комп'ютера і часу користувача.
У даній роботі я розглянула найбільш використовувані алгоритми сортування: сортування бульбашкою, вибором, вставками, метод Шелла і швидке сортування.
Метод бульбашки
Метод бульбашки (сортування бульбашкою) є, мабуть, найбільш поширеним алгоритмом сортування даних в масиві.
Назва цього методу пішло від аналогії з піднімається бульбашкою. На своєму шляху він проходить всі шари, кожен елемент, що і застосовується в цьому алгоритмі. Сам метод передбачає прохід масиву знизу вгору і порівняння найближчих елементів. Якщо якісь з перевірених елементів масиву знаходяться не в правильній послідовності, то міняємо їх місцями і продовжуємо порівнювати далі.
З погляду блок-схем алгоритм сортування бульбашкою спаданням виглядає так:
На мові програмування С ++ код сортування бульбашкою виглядає так:
Лістинг 1. bublе. срр
# inсludе lt; iоstrеam. h gt;
using namеsрaсе std;
vоid main ()
{arr [5]; i=0; ОR (i=0; i lt; 5; i ++) {
СIN gt; gt; arr [i];// Ініціалізація масиву
}
fоr (i=0; i lt; 5; i ++) {// цикл сортування бульбашкою
if (arr [i] lt; arr [i + 1]) {k=0;=a [i]; [i]=arr [i + 1]; [i + 1] =k;
}
} еm (рausе);
}
Так як на проходження всього масиву потрібно дуже багато часу, то можна зробити висновок, що алгоритм бульбашки дуже повільний і малоефективний. Тим не менш, він все ж має плюс: його можна легко покращувати за рахунок його простоти.
Розглянемо поліпшення, які можна привнести в цей алгоритм.
По-перше, можна запам'ятовувати чи проводився на даному проході як-небудь обмін, і якщо ні, то алгоритм закінчує роботу. Це дозволить уникнути зайвого проходу по масиву, коли і так зрозуміло, що він вже відсортований. Це поліпшення можна так само модернізувати, запам'ятовуючи не тільки подія обміну, а й індекс останнього обміну n. Всі пари сусідніх елементів з індексами, меншими n, вже розташовані в потрібному порядку. Подальші проходи можна закінчувати на індексі n, замість того щоб рухатися до встановленої заздалегідь верхньої межі i.
Ще одним якісним поліпшенням є модернізація алгоритму до Шейкер-сортування. Таке сортування відрізняється тим, що в ній проходи по масиву з кожни...
