Лабораторна робота 11
Тема: Сортування даних
Мета роботи: отримання практичних навичок складання і відлагодження програм сортування даних.
Теоретичні відомості
Дано множину {Аi} (i=[1;n]), елементи якої індексовано довільним чином. Небхідно індексувати {Аi} так, щоб із i < j слідувало Xi < Xj (i, j=[1;n]) (упорядкованість по зростанню) чи Xi > Xj (впорядкованість за спаданням). Процес сортування полягає у послідовних перестановках елементів множини {Аi} доти, доки їх індексація не узгодиться з їх упорядкованістю.
Сортування наданих методом обміну(метод „бульбашки”)
Основна ідея методу полягає у тому, що на кожній i-ій ітерації циклу порівнюють два сусідніх елементи Аi i Аi+1 (i=[1;n-1]). Якщо пара розташована не попорядку то елементи Ai i Ai+1 міняють місцями і реєструють факт такої перестановки. Перегляд повторюється дот тих пір, коли під час перегляду масиву від початку до кінця не буде більше перестановок.Таким чином найменший (найбільший) елемент опиниться на своєму місці у множині{Аi}.
Метод має невелику швидкодію (середня кількість порівнянь дорівнює (n*n-n)/2), є малоефективним для множин великого розміру, але має найбільш прозорий алгоритм.
Сортування наданих методом вибору
Основна ідея методу полягає у тому, що на кожній i-ій (i=[1;n-1]) ітерації зовнішнього циклу серед елементів множини {Aj} (j=[i+1;n]) шукають індекс k елементу Ak, який є найменшим (сортування по зростанню) чи найбільшим (сортування за спаданням) у порівнянні з елементом Ai і переносять цей елемент в кінець послідовності (дані Аk и Аi міняють місцями). Надалі, характерною особливістю методу є наявність двох незалежних частин послідовності – невпорядкованої (елементи, що залишилися) і впорядкованої. Метод має більшу швидкодію від попереднього, оскільки на кожній (i+1) -ій ітерації розглядається множина {X}, менша ніж на i-ій ітерації, за рахунок збільшення мінімального індексу множини на 1. Загальна кількість порівнянь наданих дорівнює n*n/2.
Сортування наданих методом включення
Основна ідея алгоритму: є впорядкована частина у яку черговий елемент поміщається (включається) так, що впорядкованість зберігається. Метод полягає у тому, що на кожній i-ій ітерації зовнішнього циклу (i=[2;n]) елемент Аi порівнюється з елементами Аj (j=[1;i-1]), і якщоАi < Аj (сортування по зростанню) чи Аi > Аj (сортування за спаданням), то елементи від Аj до Аi-1 зсувають праворуч на одну позицію, а еле-мент Аi розташовують на місці елементу Аj (таким чином елемент Xi ніби "розсовує" множину {А} з позиції j праворуч).
Кількість операцій у найгіршому випадку складає n*n/4 порівнянь і вставок. Метод можна рекомендувати для сортування малих множин.
Завдання для самостійної роботи
1. Познайомитися з задачею сортування даних
2. Вивчити основні методи сортування масивів: метод обміну, метод вибору, метод включення
3.Скласти і відлагодити окремі програми сортування даних масиву {Аi}n методами: обміну, вибору і включення.
Індивідуальне завдання синтезувати самостійно з урахуванням наступ-них вимог:
· Масив {Аi}n містить випадкові числа з інтервалу [K1;K2] кількістю у межах [10...20].
· Масив {Ai}n можна сортувати за зростанням чи за спаданням.
· Повинна бути задана нескладна умова участі елементів масиву у сортуванні (наприклад, сортування тільки елементів з парними чи непарними індексами, додатних чи від’ємних, цілих, дійсних чи текстових даних і т.д.).
Приклад виконання завдання
Елементи цілочисельного масиву {Аi}n (i=[1;n]), які є випадковими числами з інтервалу [K1;K2], відсортувати за зростанням методами обміну, вибору і включення.
// Програма сортування масиву методом обміну(метод „бульбашки)”
#include <iostream.h>
#include <conio.h>
void Sort (int A[], int n)
{ int i, found;
do {
found = 0;
for (i = 0; i <= n-1; i++)
if (A[i] > A[i+1]){
int cc= A[i]; A[i] = A[i+1]; A[i+1] = cc
found++;
}
} while (found!=0);
}
void main (void)
{ int i, Size, K1, K2;
clrscr ();
cout << endl << "Введіть розмір масиву і межі K1 та K2 змінени даних: ";
cin >> Size >> K1 >> K2;
int Array[Size];
randomize ();
for (i = 1; i <= Size; i++) Array [i] = random (K2-K1+1) + K1;
cout << endl << "Несортований масив:" << endl;
for (i = 1; i <= Size; i++) cout << Array[i];
Sort (Array, Size);
cout << endl << "Сортований масив:" << endl;
for (i = 1; i <= Size; i++) cout << Array[i];
}
Програма сортування масиву методом вибору
#include <iostream.h>
#include <conio.h>
void Sort (int in[]? Int n)
{
for (int i=0; i < n-1; i++) {
for(int j=i+1,k=s; j < n; j++)
if (in[j]<in[k]) k=j;
int c=in[k]; in[k]=in[i];in[i]=c;
}
}
void main (void)
{ int i, Size, K1, K2;
clrscr ();
cout << endl << "Введіть розмір масиву і межі K1 та K2 змінени даних: ";
cin >> Size >> K1 >> K2;
int Array[Size];
randomize ();
for (i = 1; i <= Size; i++) Array [i] = random (K2-K1+1) + K1;
cout << endl << "Несортований масив:" << endl;
for (i = 1; i <= Size; i++) cout << Array[i];
Sort (Array, Size);
cout << endl << "Сортований масив:" << endl;
for (i = 1; i <= Size; i++) cout << Array[i];
Програма сортування масиву методом включення
#include <iostream.h>
#include <conio.h>
void Sort (int in[]? Int n)
{ for (int i=1; i <= n; i++) {
int v=in[i];
for (int k=0; k<1j <=1; kj++)
if (in[k] < v) break;
for(int j=i-1;j>=k;j--)
int[j+1]=in[j];
in[k]=v;
}}
void main (void)
{ int i, Size, K1, K2;
clrscr ();
cout << endl << "Введіть розмір масиву і межі K1 та K2 зміни даних: ";
cin >> Size >> K1 >> K2;
int Array[Size];
randomize ();
for (i = 1; i <= Size; i++) Array [i] = random (K2-K1+1) + K1;
cout << endl << "Несортований масив:" << endl;
for (i = 1; i <= Size; i++) cout << Array[i];
Sort (Array, Size);
cout << endl << "Сортований масив:" << endl;
for (i = 1; i <= Size; i++) cout << Array[i];
}
Контрольнi запитання
1. Сформулюйте загальну задачу сортування даних.
2. Якими експлуатаційними показниками характеризуються методи сортування даних?
3. Викладіть суть сортування даних методами: обміну, вибору і включення.
4. Дайте порівняльну характеристику методів сортування.
5. Дайте вичерпні пояснення до розроблених програм.
