Сортиране вложки
[Член] алгоритъм
Предизвикателството е това: там е част от масив, който вече е бил подредени, а вие искате да вмъкнете останалата част от елементите на масив в сортиран част, като същевременно се поддържа системност. За да направите това, на всяка стъпка от алгоритъма избираме един от елементите на входните данни и да го поставите на нова позиция във вече подредени част на масива, докато целия набор от входни данни няма да бъдат сортирани. Метод за избор на следващия елемент на източник на масива е произволен, но е обикновено (и с цел да се получи стабилен алгоритъм за сортиране), елементите се поставят в реда на тяхното появяване във входната масива.
Тъй като само съседните елементи могат да бъдат разменени в хода на алгоритъма, всеки споделяне намалява броя на инверсии на единица. Следователно, броят на обмен е броят на инверсиите в източник на масива, независимо от изпълнението на подобно. Максималният брой инверсии в масива, чиито елементи са подредени по nonincreasing. Броят на инверсии в този масив.
Алгоритъмът работи за, където - броят на обмен на елементите на входния масив, равен на броя на инверсиите. В средата и в най-лошия случай - за. Минимални оценки възникнат в случай на подредена последователност от елементи на оригинала, най-лошото - когато те са в обратен ред.
[Член] Псевдокод
[Член] Работен пример
Един пример на алгоритъм за масива
Първият проход (втори член избутва -2)
Алгоритъмът сравнява второ звено с първия и променят местата си.
Вторият канал (трети елемент избутва -4)
Той сравнява трети с втория и суапове
Вторият и първото нещо, размяната не се изисква
Третият проход (избута четвърти -3)
Променя четвърти и трети места
Променя през третото и второто места
Вторият и първото нещо, размяната не се изисква
Четвърто пас (пети елемент избутва -1)
Променя пети и четвърти места
Променя четвърти и трети места
Променя през третото и второто места
Той се променя първата и втората позиции. Масивът се сортира.
[Член] оптимизация
[Член] Binary вложка
Сега, вместо линейна търсене на позицията, ние ще използваме двоично търсене. Следователно броят на сравнения да се промени от. Броят на сравненията е намалял значително, но за да се сложи точка на мястото му, все още трябва да се движат голям брой елементи. В резултат на това времето за изпълнение на алгоритъма в асимпотично не намалява. Binary вложка изгодно използва само в случаите, когато сравнението отнема много време, в сравнение с промяната. Например, когато ние използваме масив от дълги числа.
[Член] двупосочна вмъкване
Същността на този метод е, че вместо на сортиран част на масива, ние използваме района на изход. Първият елемент е поставен в средата на изхода зона и място за следващия елемент се освобождава от елементите на смяна наляво или надясно до мястото, където по-благоприятни. Един пример на набор от елементи
Първият проход (втори член избутва -5)
От полето за изход все още няма елементи, ние просто добавите елемента към.
Вторият канал (трети елемент избутва -7)
С двоичен търсене намерите позицията и крайната позиция, тъй като тя не трябва да се движи нищо.
Третият проход (избута четвърти -3)
С двоичен търсене намерите позицията и крайната позиция, тъй като тя не трябва да се движи нищо.
Четвърто пас (пети елемент избутва -4)
С двоичен търсене намерите позиция. Разстояние от левия край на площта на дисплея е по-малко от него нито надясно и наляво страна смяна.
Четвърто пас (пети елемент избутва -6)
Разстоянието до десния край е по-малко, отколкото в ляво, като по този начин се движат от дясната страна.
Както може да се види на изхода на структурата на поле е подобно на разлагане. а именно, ние избираме ръба, който е по-близо до нашата елемент, след което добавете тази страна на нашия елемент и да го преместите. Както можем да видим в този пример, той взе да се движи целия елемент. Поради факта, че за да вмъкнете ия елемент ще изисква промени в най-лошия случай, а не, както и окончателният брой изисква в най-лошия случай, операциите ще бъдат.