Методичні вказівки до організації самостійної роботи студентів
Одна з дій, що найбільш часто зустрічається в програмуванні — пошук. Існує кілька основних способів пошуку і для них створено багато різних алгоритмів. При виконанні роботи варто виходити з допущення, що група даних, у якій необхідно відшукати заданий елемент, фіксована.
Сортування — це задача розташування довільних об'єктів у порядку (не-) зменшення чи (не-)зростання деякої ознаки. Існує велика кількість методів сортування, що відрізняються друг від друга як тимчасовою складністю, так і універсальністю.
Лінійний пошук
Якщо немає ніякої додаткової інформації про розшукувані дані, то очевидний підхід — простий послідовний перегляд масиву зі збільшенням крок за кроком тієї його частини, де бажаного елемента не виявлено.Умови закінчення пошуку: елемент знайдено чи весь масив переглянуто і збігу не виявлено.
Пошук розподілом навпіл (двійковий пошук)
Пошук може бути більш ефективним, якщо дані будуть упорядковані. Основна ідея – вибрати випадково деякий елемент аm і порівняти його з аргументом пошуку х. Якщо він дорівнює х, то пошук закінчується, якщо він менше х, то всі елементи з індексами, меншими чи рівними m, можна виключити з подальшого пошуку; якщо ж він більше х, то виключаються індекси, більші чи рівні m.
Сортування вставками
Нехай потрібно упорядкувати масив 
за зростанням пропонується використовувати наступний підхід: для 
, кожен елемент 
будемо вставляти в потрібне місце серед упорядкованих раніше елементів 
, розсовуючи їх за рахунок видалення . Цей метод у явному виді рідко використовується на практиці, однак покладена в його основу ідея добре працює, коли потрібно вставити новий елемент у вже упорядкований масив.
|
|
|
Метод пухирця
Ідея методу полягає в упорядкуванні всіх пар сусідніх елементів. Масив проглядається зліва направо і, якщо xi > xi+1 (i=1…n-1), то вони міняються місцями. При цьому i-й елемент (крім першого й останнього) бере участь у двох порівняннях, а це значить, що максимальний елемент масиву буде переміщатися («спливати») до правого кінця масиву і до кінця проходу виявиться останнім. За наступний прохід «спливе» другий по величині елемент і т.д., поки всі елементи не займуть свої місця. Очевидно, для цього буде потрібно не більш n-1 проходів.
Сортування перерахуванням
Для кожного елемента масиву X(n) вважаємо, скільки елементів менше його, тобто фактично знаходимо його положення в упорядкованому масиві. Для збереження цієї інформації можна використовувати масив лічильників C(n). Тоді значення Сi+1 визначає положення елемента xi у результуючому відсортованому масиві R(n).
|
|
|
Швидке сортування
Цей алгоритм одержав широке поширення в багатьох прикладних програмах. Однак ефективність його використання істотно залежить від числа елементів сортуемого масиву, а також характеру розподілу цих даних. Отже:
— вибирається який–небудь елемент (x) (звичайно знаходиться в середині послідовності). Будемо переглядати масив ліворуч доти, поки не знайдемо елемент аi>x, потім будемо переглядати масив праворуч, поки не зустрінеться аj<x. Тепер поміняємо місцями ці два елементи і продовжимо наш процес перегляду й обміну, поки обидва перегляди не зустрінуться десь у середині масиву (значення i та j рівні). У результаті виявиться, що масив розбито на дві половини із ключами, меншими або рівними x, і більшими або рівними x, а сам елемент x буде знаходитися в необхідному місці; 
— ітераційно повторюємо процес 1 для кожної з отриманих половин (у перший раз одержимо чотири піддіапазону вихідної послідовності) доти, поки значення індексів для кожного вкладеного діапазону чи будуть рівні, чи змінять відношення. У результаті ми одержимо упорядковану послідовність.
Сортування злиттям
Це алгоритм об'єднання двох відсортованих масивів в один. Розглянемо два відсортованих по неубуванню масиву X(n) і Y(m). Нехай необхідно об'єднати їх в один масив Z(n+m), також упорядкований. Вирішимо цю задачу в такий спосіб: з кожної пари мінімальних елементів масивів X і Y (починаючи з x1 і y1) вибираємо найменший і записуємо його в Z, а в масиві, з якого був узятий цей елемент, збільшуємо на одиницю індекс наступного, ще не розглянутого елемента. Так продовжуємо, поки один з масивів не вичерпається. Якщо першим вичерпався масив X, то залишок Y цілком переписуємо в Z, якщо першим вичерпався Y, то в Z переписуємо залишок X .
|
|
|
Приклад 7 Реалізація методу “швидкого” сортування
#include<iostream.h>
#include<stdio.h>
#define b=16
int n=6;
int a[6];
int i,j,l,r=6;
void swap(int*,int*);
void quicksort(int,int);
void part(int,int,int&,int&);
Int main()
{ for(int k=1;k<=n; k++)
{cout << "input а["<<k<<"] of massive \n";
cin >> a[k]; }
quicksort(1,n); // вызов функции быстрой сортировки
for(k=1; k<=n; k++)
{printf("a[ %d ]= %d \n",k,a[k]);}
cin>>k;
return 0;
}
void swap(int* p,int* q)
{ int prom;
prom=*p;
*p=*q;
*q=prom; }
void quicksort(int l,int r) //функция быстрой сортировки
{ int i,j; i=l; j=r;
{ part(l,r, i, j);
if(i<r) quicksort(i,r); //переход к сортировке слева
if(j>l) quicksort(l,j); } // переход к сортировке справа
}
void part(int l,int r,int &i,int &j)
{ int x ; i=l; j=r; x=(l+r)/2;
|
|
|
do { while (a[i]<a[x]) i++; //просмотр: найдём a[j]> a[x]
while(a[j]>a[x]) j--; //просмотр: найдём a[j]< a[x], меняем местами
if(i<=j)
{ swap(&a[i],&a[j]); //обмен этих элементов
i++;j--; }
} while(i<j); }
Контрольні запитання
1. Як змінити алгоритм пошуку найбільшого з уведених чисел, щоб він знаходив найменше число ?
2. Запропонуйте алгоритм не двоїчного, а троїчного пошуку.
3. Що потрібно змінити в алгоритмі обмінного сортування, щоб першими займали свої місця не великі числа, а маленькі ?
4. Поліпшите алгоритм обмінного сортування так, щоб робота припинялася, якщо проходження масиву не викликало жодного обміну.
5. Розробіть алгоритм злиття масивів a і b з упорядкованими ділянками довжини d.
6. Розробіть алгоритм злиття двох масивів з упорядкованими ділянками довільної довжини. Як визначити кінець упорядкованої ділянки?
7. Чи зміниться складність алгоритму злиття, якщо зливати не по два, а по три масива?
Дата добавления: 2018-04-15; просмотров: 350; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!