Деф.Инверсия е дв. ключове, които не са в необходим ред в файла.
Св. Сорт. чрез вмъкване и по метода на мехурчето изискват линеен брои сравнения и размени за фаилове с най – мн. константен. брой инверсии, съответни на всеки елемент.
Сортировката чрез вмъкване е подходяща за почти сортиране файлове, където трябва да се добявят няколко елем. Докато метода на мехурчето и селект. сортировка не са.
Св. Сортир. чрез вмъкване използва лин. бр. сравнения. и размени за файлове с най – многоконстант. брой. елем. имащи повече от констант. бр. съответстващи инверсии.
Св. Селективната сортировка работи за линейно време при файлове с големи елем и малки ключове.
СортировканаШел.Примериисвойства.
Сорт. на Шел е разшир на селект. сорт, к-то печели скорост, като позволява. размяна на елем, далеч един от др. Идеята е да пренаред. фаил, за да му дад св., че вземаики всеки h елем.(като започнем от някъде), пораждаме сортиран фаил. Такъв фаил се казва че е h сортиран. h сорт. фаил представлява h независ сорт фаилове. поставени последов.
Пример: В сл. стъпката е N/2 = 4; След 1 -вата. итерация пак. сорт. с стъпка 2. и после с стъпка 1.
void shellsort (Item a[], int l, int n)
{ int i, j, h;
for ( h =1; h<=(r-l)/9; h = 3*h+1); for (; h>0;h /=3)
for (i = l+h); i <=r; i++)
{ int j = i; Item v = a[i];
while (j > = l+h) && less(v, a[j - h]))
{ a[j] = a[j-h]; j -=h;} a[j] = v;
Използват се ограничители и после се заменя всяко срещане на l с h в сортиров. чрез вмъкване, прог. прави h сорт. на фаил.
Един от наи сложните въпроси при Шел сортировката е каква редица на нарастване да се използва. В п-ката обикнов.се използ. редици, които намал. геометрично
Св: Резултата от h – сортир на фаил, к-то е k - нареден, е фаил, к-то e и h и k нареден.
