Метод вставок

Елементи масиву розміром N умовно розділяють на готову (упорядковану) послідовність і вхідну послідовність. Спочатку в готову послідовність включається один елемент – a[0]. Вхідна послідовність починається з елемента a[1]. Ці елементи порівнюються, і якщо a[1]<a[0], елементи обмінюються місцями. На кожній ітерації вибирається перший елемент вхідної послідовності й передається в готову послідовність шляхом вставки. Місце вставки визначається порівнянням цього елемента з елементами готової послідовності. Ітерації тривають, поки довжина готової послідовності не стане рівній N.

Запишемо функцію сортування методом вставок insertSort, у списку аргументів якої: *a - покажчик на масив; num - розмір масиву; &mov - посилання на змінну, що враховує число пересилань.

void insertSort(int *a, int num, int &mov){

int i, j, key;

for(i = 1; i <num; i++){ //Взяти 1-й ел-т вхідної посл-сті

key = a[i];

mov++;

j = i - 1;

while (a[j] > key){ //Порівняти ел-ти готової посл-ти з key,

a[j+1] = a[j]; //Ел-ти > key зсунути вправо на 1 позицію

mov++;

j--;

}

if(a[j+1]!=key){ //Вилучити перестановки однакових ел-тів

a[j+1] = key; //Вставити key у місце, що звільнилося mov++;

display(a, num);

}

}

}

Наведемо приклад сортування методом включень (білі комірки - вхідна послідовність, сірі комірки - готова послідовність):

Вихідний масив
1-я ітерація
2-я ітерація
3-я ітерація
(N-1)-я ітерація, вхідна послідовність вичерпана

Відзначимо, що у функції сортування insertSort завдяки умові if(a[j+1]!=key) виключені ітерації, при яких не виконується вставка (у даному прикладі – це 3-я ітерація).

9.1.4. Порівняння ефективності алгоритмів сортування

Ефективність того або іншого алгоритму сортування оцінюється інтегральним показником – тривалістю виконання сортування. Основними операціями, на які затрачається машинний час, є порівняння й пересилання.

Операція порівняння (наприклад, типу a[j+1]>a[j]) – один з основних гальмуючих факторів, особливо, якщо виконується сортування рядків. Наприклад, для з'ясування, який із двох схожих рядків більше, доводиться порівнювати букву за буквою на великій довжині рядка. При роботі з числовими масивами одна операція порівняння виконується значно швидше, ніж при порівнянні рядків. Однак загальне число порівнянь у процесі сортування росте пропорційно квадрату розміру масиву. Можна показати, що робота кожного з розглянутих методів сортування (обміну, вибору й вставок) характеризуються приблизно однаковим числом порівнянь , де – розмір масиву.

Оскільки по числу порівнянь розглянуті три методи сортування майже рівноцінні, порівняльну ефективність методів потрібно визначати по числу пересилань. До пересилань ставляться операції присвоювання (наприклад, для перестановки двох елементів масиву за допомогою функції swap потрібно виконати три пересилання). Число пересилань у наведені вище функціях сортування зберігається в змінної mov (див. пункти 9.1.1 – 9.1.3).

9.1.5. Генерація псевдовипадкових чисел

Функція rand()%max при заданому параметрі max фактично генерує одне ж і ту послідовність випадкових чисел. Щоб при кожному запуску генератора породжувалася нова послідовність псевдовипадкових чисел, потрібно використати функцію srand, що встановлює точку відліку при генерації чисел і ставиться перед функцією rand, наприклад,

#include <stdlib.h>

#include <time.h>

...

srand((unsigned)time(NULL));

for (int i=0; i<n; i++)

a[i] = rand()%max;

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

Скласти програму для сортування масиву випадкових чисел трьома методами: обміну, вибору й включень. Проаналізувати ефективність різних методів сортування.

9.3. Методичні вказівки

1. Програма повинна мати наступну структуру:

<Підключення необхідних бібліотек>

<Ініціалізація змінних>

<Цикл по розміру масиві>

<Створення i ініціалізація дінамичного масиву >

<Печатка вихідного масиву>

<Копіювання вихідного масиву>

<Сортування копії масиву методом Buble>

<Сортування копії масиву методом Selection>

<Сортування копії масиву методом Insertion>

<Виведення результатів сортування>

Операції ініціалізації, виведення, сортування масиву мають бути реалізовані за допомогою функцій.

2. На етапі налагодження програми показувати на екрані вихідний масив і результаті ітерації. Потім при відображенні результатів сортування (див. наступний пункт) відключити це виведення.

3. Результати сортування різними методами (кількість пересилань) потрібно вивести у вигляді таблиць:

num Buble Select Insert

.......................

.......................

4. Тричі запустити програму. Знайти середнє арифметичне число пересилань для кожного розміру масиву й трьох методів сортування.

5. На основі отриманих даних побудувати в електронних таблицях Excel графіки залежностей середньо арифметичного числа пересилань від розміру масиву для трьох методів. По осі абсцис – значення num, по осі ординат – відношення mov/num.

9.4. Зміст звіту

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

2. Код програми.

3. Скріншот вікна з результатами роботи програми.

4. Таблиця й графіки результатів.

5. Висновки.

10. Лабораторна робота 9. «Рядки» (4 рік.)

Ціль роботи:. Освоїти прийоми роботи із символами й рядками. Навчитися застосовувати бібліотечні функції обробки рядків у реальних завданнях.

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

10.1.1. Функції для роботи із символами

Для зберігання символів використовується базовий тип char. В основу кодування символів покладена кодова таблиця ASCII, що встановлює відповідність між символом (буквою, цифрою, знаком пунктуації й т.д.) і кодом (двійковим числом).

У мовах С/С++ передбачені спеціальні функції, призначені для роботи із символами (табл. 10.1). Частина функцій перевіряють одиночні символи й повертають ненульове значення (true) або нуль (false). Наприклад, isdigit(c) дозволяє перевірити, чи є параметр c однієї із цифр між 0 і 9. Інша частина функцій у таблиці 10.1 забезпечує конвертування регістра букв. Так, tolower(c) повертає версію букви c у нижньому регістрі, тобто малу літеру. Наприклад, інструкція cout <<tolower('F') виведе на екран символ f.

Наступний фрагмент коду використовується як елемент циклу do-while, у якому користувач для продовження циклу повинен увести 'Y'. Цикл буде виконуватися незалежно від того, у якому регістрі уведений символ: 'y' або 'Y'.

do{ // тіло циклу

}

while (toupper(choice) == 'Y')

Параметром функцій у таблиці 10.1 є змінна c типу char або int, а для звертання до функцій підключається заголовний файл ctype.h.

Табл. 10.1. Функції для роботи із символами

Тип	Функція	Опис
Int	isalnum(c)	повертає true, якщо c – буква або цифра
Int	isalpha(c)	повертає true, якщо c – буква
Int	isblank(c)	повертає true, якщо c – пробіл або символ табуляції
Int	isdigit(c)	повертає true, якщо c – цифра
Int	islower(c)	повертає true, якщо c – символ у нижньому регістрі
Int	isupper(c)	повертає true, якщо c – символ у верхньому регістрі
Int	isspace(c)	повертає true, якщо c – пробіл, табуляція, повернення каретки, новий рядок
Int	tolower(c)	повертає символ c у нижньому регістрі
Int	toupper(c)	повертає символ c у верхньому регістрі

10.1.2. Строкові константи

Щоб із символів набирати фрази, використовуються строкові константи, які беруться в подвійні лапки й можуть складатися з букв, цифр, розділових знаків, пробілів, спеціальних символів. Наприклад, ціна

"120,00 грн."

або речення

"love me love my dog!"

є строковими константами. Рядок займає суцільну область пам'яті. Ця область завершується нульовим символом '\0' (ASCII-код нульового символу 0), що автоматично підставляється в кінець рядка: