Сортировка чрез вмъкване

Сортировка чрез вмъкване

Сортировката е процес, подреждащ множество елементи по ключове, за които е определен предварително някакъв ред на предхождане (или следване)

Сортировката може да бъде вътрешна – извършва се в оперативната памет, и външна – върху външни запаметяващи устройства.

Основен критерий за ефективността на сортировката е броят сравнения (при вътрешната сортировка), или броят на входно-изходните операции(при външната). Тук се разглеждат само случаите на вътрешна сортировка върху числени множества данни, представени чрез масиви.

Размяната се състои в обмен на двете стойности посредством междинна променлива, например “с”, и има вида:

c=a[i]; a[i]=a[j]; a[j]=c;

Сортирането чрез пряко вмъкване се състои в следното. За всеки елемент с номер от j =2 до j=n се обхождат елементите с номера от l= j-1 до l=1. Ако се стигне до число, по-голямо от числото k=a[j], това число се премества надясно, а на освободеното място се вмъква числото k.

Оценките на метода са следните:

Тср.мин.=n-1; Тср.ср.=(n*n+n-2)/4; Тср.макс.=(n*n+n)/2-1;

Траз.мин.=2(n-1); Траз.ср.=(n*n+9n-10)/4; Траз.макс.=(n*n+3n-4)/2.

Общата сложност на алгоритъма е пропорционална на n*n, т.е О(n)=n*n.

Следващата “схема” пояснява метода.

73 32 26 82 3 начално състояние

32 73 26 82 3 i=2

26 32 73 82 3 3

26 32 73 82 3 4

3 26 32 73 82 5 подреден масив

В общия случай задачата се формулира така: Да се напише програма на С/С++, която въвежда 10 произволно взети числа, сортира ги по метода “сортировка чрез пряко вмъкване” и ги извежда сортирани (във възходящ ред) на екрана на монитора.

Следващата функция Sort_Ins() реализира този метод на сортировка.

void Sort_Ins(){

float k;

int l,j;

do {

l=j-1;

=0){

a[l+1]=a[l];

l=l-1; }

a[l+1]=k;

j=j+1;}

while(j

}

За решаване на задачата, може да се използва дадената функция.

Функцията реализира сортировката чрез последователно търсене на мястото в подрередицата, където да се вмъкне i-тия елемент.

Ако се вземе под внимание, че подредицата, в която се извършва вмъкването е сортирана, може да се реализира по-ефективна операция на вмъкване, ако последното се реализира “двоично”, т.е. чрез т.нар. “вмъкване чрез двоично търсене”.

При двоичното търсене се разделя сортираната подредица на две и се определя в коя половина да продължи вмъкването, след което се прави разделяне (на две) на избраната половина ...и т.нат. до определяне на мястото на вмъкване на i-тия елемент. Следващата функция реализира двоично търсене.

int Binary_search(int l, int r; real x){

int m;

while (l

m=(l+r)/2;

if(x

r=m-1;

else

l=m+1;

}

return l; }

След като се намери мястото на вмъкване, всички елементи от подредената подредица, по-големи от вмъквания, трябва да се изместят с една позиция надясно.

Въпроси по темата и задачи за изпълнение:

1. Напишете формулата, даваща асимптотичната сложност на метода “сортиране чрез пряко вмъкване” .

2. Напишете програма на С/С++, която използва функцията Sort_Ins(), въвежда N на брой числа и ги сортира във възходящ ред, след което ги извежда на екрана на монитора сортирани.

Каталог: docs -> Bachelor -> II%20Kurs -> Sem%20IV -> SAA
SAA -> Вероятностни алгоритми Цел: Упражняване в създаването и програмната реализация на вероятностни алгоритми Теоретична част
SAA -> Лекция №2 алгоритмично-програмни конструкции видове алгоритми
SAA -> Дървета Цел
SAA -> Евристически алгоритми
SAA -> Лекция №4 с о р т и р а н е и с м е с в а н е същност на сортирането
SAA -> Цел: Запознаване с метода за създаване на ефективно по – рекурсия. Създаване и използване на рекурсивни функции при решаване на сложни задачи. Теоретична част
SAA -> Лекция №3 Сложност на алгоритмите
Sem%20IV -> Eлектротехника и електроника
SAA -> Задача за "Ход на коня". Задача 1: Ход на коня
SAA -> Усвояне на похватите за представяне на графи в по, програмна реализация на графи и решаване на задачи над графи

Изтегляне 45 Kb.

Сподели с приятели: