Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Сұрыптау алгоритмдерінің түрлері және бейнеленуі. Мысал келтіріңіз





Сұрыптау-берілген обьектілер жиынын (сандарды) ұсынылған реттілікпен қайта теріп орналастыру процесі.

Жиымдарды сұрыптау жылдамдығы әр түрлі болады. Қарапайым сұрыптау тәсілдері n*n рет салыстыруды керек етеді, мұндағы n- жиым элементтері саны; ал жылдам сұрыптау тәсілі n*ln(n) рет салыстыруды қажет етеді. Қарапайым тәсілдер түсінуге жеңіл, өйткені алгоритмі түсінікті. Күрделі тәсілдер аз әрекеттер санын керек еткенмен, операциялары күрделірек болады, сондықтан элементтер саны аз жиымдарға қарапайым тәсілдерді қолданған дұрыс.

Қарапайым тәсілдер 3 топқа бөлінеді:

· Жай таңдау жолымен сұрыптау

Жиымның ең кіші элементі анықталады да, ол бірінші элементпен орын ауыстырады. Қалған элементтермен де осы тәсіл қайталанады.

           
    минимум      

int I, min, n_min,j;

for(int 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;}

· Жай енгізу тәсілімен сұрыптау

Жиым элементтері 2-ге –бастапқы тізбекке және дайын тізбекке бөлінеді. Әрбір адымда I=2 нөмірімен бастап берілген тізбектен I-ші элемент алынады да, ол дайын тізбектің керекті жеріне орналастырылады. Мұнан кейін I-ге 1 қосылады да, сол әрекеттер қайталанады.

           
Дайын тізбек Бастапқы тізбек

Керекті орынды іздеу кезінде оң жақтағы келесі элементпен орын ауыстыру қарастырылады, яғни таңдалып алынған элемент сұрыпталғандардың J=I-1 нөмірінен басталатын кезекті элементімен салыстырылады. Егер таңдалып алынған элемент a[I]-ден артық болса, онда ол сұрыпталғандар ішіне қосылады, әйтпесе a[J] бір орынға ығысады да, таңдалған элемент сұрыпталғандар ішіндегі келесі элементпен салыстырылады. Керекті орынды іздеу әрекеті екі жағдайда:

· Егер a[I]> a[J] болатын элемент табылса;

· Дайын тізбектің сол жақ шетіне жеткен кезде аяқталады.

Мысалы:
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; //элементті кірістіріп қою

}

· Жай алмастыру тәсілімен сұрыптау

Мұнда ең соңғыдан бастап, екі элемент салыстырылады да, қажет болса, орындары алмастырылады. Осындай әрекет нәтижесінде ең кіші элемент жиымның ең сол жақ шетіне ығысады. Қалған жиым элементтері үшін де осы процесс қайталанады.

           

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;}

 

Date: 2015-09-05; view: 1450; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию