Селективна сортировка. Този алгор. раб. по сл. начин 1-во намира най-малкият елемент от масива и го разменя с този от 1-ва позиц. После намир 2-я най-малък ел. и го разм. с този от 2 поз. Продълж. по този нач докато целия мас. се сортира. Методът се нар.селек.сорт.защ.той раб чрез повта-рящ се избор на мин.оставащ елемент.
Пример с числа :
void selection (Item a[], int l, int r)
{ int i, j;
for (i = l; i< r; i++)
{ int min = i;
for (j = i+l; j <= r; j++)
if (less(a[j], a[min])) min = j;
exch (a[i], a[min]);
}}
Вътр. цикъл представлява само сравнение, за да провери текущия елем. с намер. наи малък. Вънщният цик. разменя елем. Броят на размените е N -1. Времето на изпълн. се доминира от бр. на размен. Този брой е пропорц на N квадр.Недостатък на сорт. е че вр. за изпълн зависи съвсем малко от вече подредените елем. Методът е добър за сортир. на фаилове с огромни елем. и малки ключове.
Сортировка чрез вмъкване:
Този метод работи по сл. начин: елем. се разглеждат един по един вмъкв. всеки от тях на подходящ. място. сред вече сортир.(запазваики ги по този начин сортирани). Необходимо е да се направи място за вмъквания елем., като преместв. по – гол. елем с 1 поз надясно и после вмъкв. елем. във вакантната. поз.
Пример с числа
Програмна реализация
void insertion(Item a[], int l, int r)
{ int i;
for (i = r; i >l; i--) compexch (a[i-1], a[i]); for (i = l+2; l<=r; i++)
{ int j = i; Item v = a[i]; while (less(v, a[j-1]))
{ a[j] = a[j-1]; j--; )
a[j]= v; }}
Програмата първо поставя най – малкият елем.на мас. на 1 –ва поз. , така че този елем. да служи като ограничител. Във бтр цикъл тя прави просто присвояване в место размяна. Прогр. завърщ. втр. цикъл., корато вмъкв. елем. е в същата позиция. За всяко i тя сортира елем. a[i]…..a[i-1], които са по – гол. от а[i], след което поставя a[i] в подходяща позиция.
Сподели с приятели: |
