Лабораторна робота № 8

Тема: Складання програм на сортування масивів. Пошук у відсортованому масиві

Мета: Навчитись сортувати числові масиви по зростанню або спаданню та здійснювати в них пошук заданих елементів.

1 Короткі теоретичні відомості

Сортування масивів. Сортування - це процес перегрупування заданої множини об'єктів у деякому встановленому порядку. Числові масиви сортуються зазвичай по зростанню або по спаданню. Масиви символьних змінних можуть сортуватися по алфавіту.

Сортування масивів розподіляються за швидкодією. Існують прості методи сортування, які вимагають n*n операцій порівняння, де n - кількість елементів масиву. Швидкі методи сортування вимагають n*ln(n) операцій порівняння. Прості методи зручні для пояснення принципів сортування, тому що вони мають прості й короткі алгоритми. Ускладнені методи вимагають меншої кількості операцій порівняння, але алгоритм більш складніший, тому для невеликих масивів прості методи більш ефективні. Складні методи дають ефект для масивів великих розмірів.

Прості методи поділяють на три основні категорії:

- сортування масивів методом простого включення;

- сортування масивів методом простого вибору;

- сортування масивів методом простого обміну.

Сортування масивів методом простого включення (вставки). При застосуванні даного методу для сортування масивів елементи масиву діляться на вже готову відсортовану послідовність і початкову. При кожному кроці, починаючи з і=2, з початкової послідовності витягується 1- ий елемент і вставляється на потрібне місце готової послідовності, потім і збільшується на 1, витягується 2-ий елемент і вставляється на потрібне місце готової послідовності і т.д.

готова	початкова

У процесі пошуку потрібного місця здійснюються пересилання елементів більше обраного на одну позицію вправо, тобто обраний елемент порівнюють із черговим елементом відсортованої частини, починаючи з J:=I-1. Якщо обраний елемент більше a[I], то його включають у відсортовану частину, в іншому випадку a[J] зсувають на одну позицію, а обраний елемент порівнюють із наступним елементом відсортованої послідовності. Процес пошуку потрібного місця закінчується при двох різних умовах:

- якщо знайдено елемент a[J]>a[I];

- досягнуть лівий кінець готової послідовності.

Нижче наведено фрагмент програми для сортування методом простого включення.

int i,j,x;

for(i=1;i<n;i++)

{

x=a[i];//запам'ятали елемент, що будемо вставляти

j=i-1;

while(x<a[j]&&j>=0)//пошук потрібного місця

{

a[j+1]=a[j];//зсув вправо

j--;

}

a[j+1]=x;//вставка елемента }

Сортування масивів методом простого вибору. Не обмежуючи загальності, будемо розглядати сортування масиву по зростанню, тобто будемо на початок масиву ставити мінімальний елемент. Суть методу простого вибору полягає в наступному. Вибирається мінімальний елемент масиву й міняється місцями з першим елементом масиву. Потім процес повторюється з елементами, що залишилися, і т.д. Процес сортування елементів масиву проілюстровано в табл. 8.1.

Таблиця 8.1. Процес сортування елементівмасиву методом простого вибору

				2 min
			5 min
		12 min
						18 min
				44 min
						55 min

Фрагмент програми для сортування методом простого вибору.

int i,min,n_min,j;

for(i=0;i<n-1;i++)

{min=a[i];n_min=i;//пошук мінімального

for(j=i+1;j<n;j++)

if(a[j]<min){min=a[j];n_min=j;}

a[n_min]=a[i];//обмін

a[i]=min; }

Сортування масивів методом простого обміну. Суть методу простого вибору полягає в наступному. Порівнюються й міняються місцями пари елементів, починаючи з останнього. У результаті перейменування елемент масиву виявляється най лівішим елементом масиву. Процес повторюється з елементами, які залишились. Процес сортування елементів масиву проілюстровано в табл. 8.2.

Таблиця 8.2. Процес сортування елементівмасиву методом простого обміну

Наведемо фрагмент програми для сортування методом простого обміну.

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

for(int j=n-1;j>=i;j--)

if(a[j]<a[j-1])

{int r=a[j];a[j]=a[j-1];a[j-1]=r;} }

Пошук у відсортованому масиві. У відсортованому масиві використовується дихотомічний (бінарний) пошук. При послідовному пошуку потрібно в середньому n/2 порівнянь, де n – кількість елементів у масиві. При дихотомічному пошуку потрібно не більше m порівнянь, якщо n- m-а ступінь 2, якщо n не є ступенем 2, то n<k=2^m.

Масив ділиться навпіл S:=(L+R)/ 2+1 і визначається в якій частині масиву перебуває потрібний елемент Х. Так як масив упорядкований, те якщо a[S]<X, те шуканий елемент перебуває в правій частині масиву, інакше - перебуває в лівій частині. Обрану частину масиву знову треба розділити навпіл і т.д., доти, поки границі відрізку L й R не стануть рівні.

Нижче наведено фрагмент програми для пошуку у відсортованому масиві.

S=(L+R)/2=4

int b;

cout<<"\n=?";cin>>b;

int l=0,r=n-1,s;

do

{

s=(l+r)/2;//середній елемент

if(a[s]<b)l=s+1;//перенести ліву межу

else r=s;//перенести праву межу

}while(l!=r);

if(a[l]==b)return l;

else return -1;

Дата добавления: 2015-07-17