Olgaritmizazziya лабки язык С 4 вариант / лб10 / АіП - Практична робота №10
.docПрактична робота №10
Тема: Створення програм, що обробляють масиви величин різного типу. Двовимірні масиви: Сортування даних.
Мета: навчитися здійснювати впорядкування масивів даних за різними принципами. Отримати практичні навички використання найпростішого алгоритму сортування.
Теоретична частина
Бульбашкове сортування
Алгоритм складається з повторюваних проходів по сортованого масиву. За кожен прохід елементи послідовно порівнюються попарно і, якщо порядок в парі невірний, виконується обмін елементів. Проходи по масиву повторюються N-1 раз або доти, поки на черговому проході не виявиться, що обміни більше не потрібні. А це означає - масив відсортований. При кожному проході алгоритму по внутрішньому циклу, черговий найбільший елемент масиву ставиться на своє місце в кінці масиву поруч з попереднім «найбільшим елементом», а найменший елемент переміщається на одну позицію до початку масиву («спливає» до потрібної позиції як бульбашка в воді, звідси і назва алгоритму).
Приклад коду бульбашкового сортування
for (int i=n-1; i>=0; i--)
{
for (int j=0; j<i; j++)
{
if (a[j] > a[j+1])
{
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
Сортування вставками
На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію в уже відсортованому списку, доти, поки набір вхідних даних не буде вичерпаний. Метод вибору чергового елемента з вихідного масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються по порядку їх появи у вхідному масиві. Наведений нижче алгоритм використовує саме цю стратегію вибору.
Приклад коду сортування вставками
int i, j, value;
for(i = 1; i < n; i++)
{
value = a[i];
for (j = i - 1; j >= 0 && a[j] > value; j--)
{
a[j + 1] = a[j];
}
a[j + 1] = value;
}
Сортування вибором
Кроки алгоритму: знаходимо номер мінімального значення в поточному списку, проводимо обмін цього значення зі значенням першої невідсортованої позиції (обмін не потрібен, якщо мінімальний елемент вже знаходиться на даній позиції), тепер сортуємо хвіст списку, виключивши з розгляду вже відсортовані елементи. Для реалізації стійкості алгоритму необхідно в пункті 2 мінімальний елемент безпосередньо вставляти в першу невідсортовану позицію, не змінюючи порядок інших елементів.
Приклад коду сортування вибором
for (int i = 0; i < length - 1; i++) {
/* встановлюється початкове значення мінімального індексу */
int min_i = i;
/* знаходиться індекс мінімального елемента */
for (int j = i + 1; j < length; j++) {
if a[j] < a[min_i]) {
min_i = j;
}
}
/* міняємо значення місцями */
int temp = array[i];
array[i] = array[min_i];
array[min_i] = temp;
}
Контрольні питання
Що таке сортування даних? Де і з якою метою можна застосовувати цей процес?
Перерахуйте відомі вам алгоритми сортування.
Охарактеризуйте метод сортування лінійним вибором елемента.
Охарактеризуйте метод мінімального (максимального) елемента.
Охарактеризуйте метод сортування обміном ("бульбашкове" сортування).
Охарактеризуйте метод човникового сортування;
Охарактеризуйте метод сортування вставками.
В чому, на вашу думку, полягають переваги і недоліки методу «Бульбашка»?
В квадратному двовимірному розмірі здійснити сортування елементів головної діагоналі в спадаючому порядку. Результат відобразити на екрані. Використати метод вставок.
В квадратному двовимірному розмірі здійснити сортування елементів бічної діагоналі в спадаючому порядку. Результат відобразити на екрані. Використати метод вибору.
Розробити програму, що здійснює сортування за зростанням будь-якого рядка двовимірного масиву. Номер рядка отримати з клавіатури, а результат відобразити на екрані. Використати метод «бульбашки».
Розробити програму, що здійснює сортування за зростанням будь-якої колонки двовимірного масиву. Номер колонки отримати з клавіатури, а результат відобразити на екрані. Використати метод вставок.
Розробити програму, що переписує двовимірний масив в одновимірний і сортує його в порядку спадання. Використати метод вибору.
Розробити програму, що переписує в одновимірний масив елементи головної і бічної діагоналей. Отриманий масив відсортувати за зростанням і відобразити на екрані. Використати метод «бульбашки».
Розробити програму, що сортує за спаданням елементи, розміщені над головною діагоналлю, переписавши попередньо їх до одновимірного масиву. Самі елементи діагоналі не враховуються. Використати метод вставок.
Розробити програму, що сортує за зростанням елементи, розміщені над бічною діагоналлю, переписавши попередньо їх до одновимірного масиву. Самі елементи діагоналі не враховуються. Використати метод вибору.
Розробити програму, що сортує за зростанням елементи, розміщені під головною діагоналлю, переписавши попередньо їх до одновимірного масиву. Самі елементи діагоналі не враховуються. Використати метод «бульбашки».
Розробити програму, що сортує за спаданням елементи, розміщені під бічною діагоналлю, переписавши попередньо їх до одновимірного масиву. Самі елементи діагоналі не враховуються. Використати метод вставок.
Розробити програму, що сортує в спадному порядку елементи, розміщені «по контуру» квадратної матриці. Використати метод вибору.
Нехай є двовимірний масив з непарною кількістю рядків і колонок. Занести до окремого одновимірного масиву елементи з центрального рядка і колонки. Отриманий масив відсортувати за спаданням. Використати метод «бульбашки».