Сортирање је основна операција у којој су елементи низа уређени у одређеном редослиједу како би се побољшала могућност претраживања. Једноставним речима, подаци се сортирају тако да се могу лако претраживати.
Цомпарисон Цхарт
| Основа за поређење | Сортирање уметања | Сортирање сортирања |
|---|---|---|
| Басиц | Подаци се сортирају убацивањем података у постојећи сортирани фајл. | Подаци се сортирају одабиром и стављањем узастопних елемената на сортирану локацију. |
| Природа | Стабле | Нестабилан |
| Процес који треба слиједити | Елементи су претходно познати, док се локација за њихово тражење претражује. | Локација је раније позната, док се елементи претражују. |
| Непосредни подаци | Инсертион сорт је техника сортирања уживо која се може бавити непосредним подацима. | Не може се бавити непосредним подацима, мора бити присутан на почетку. |
| Бест цасе цомплекити | На) | О (н 2 ) |
Дефиниција сортирања уметања
Инсертион сортирање ради уметањем скупа вриједности у постојећи сортирани фајл. Он конструише сортирани низ убацивањем једног елемента у исто време. Овај процес се наставља док се цијели низ не сортира неким редослиједом. Примарни концепт који стоји иза сортирања уметања је уметање сваке ставке на одговарајуће место у коначној листи. Метод сортирања уметања чува ефективну количину меморије.
Рад сортирања Инсертион
- Користи два низа поља у којима се чувају сортирани подаци и други на несортираним подацима.
- Алгоритам за сортирање ради док не постоје елементи у несортираном скупу.
- Претпоставимо да у низу постоје елементи 'н' броја. У почетку, елемент са индексом 0 (ЛБ = 0) постоји у сортираном скупу. Преостали елементи се налазе у несортираној партицији листе.
- Први елемент несортираног дијела има индекс поља 1 (ако је ЛБ = 0).
- Након сваке итерације, он бира први елемент несортиране партиције и убацује га на одговарајуће место у сортираном скупу.
Предности сорте Инсертион
- Лако се имплементира и веома је ефикасна када се користи са малим скупом података.
- Потреба додатног меморијског простора за сортирање уноса је мања (тј. О (1)).
- Сматра се да је то техника сортирања уживо, јер се листа може сортирати по пријему нових елемената.
- Он је бржи од других алгоритама за сортирање.
Пример:
Дефиниција сортирања сортирања
Сортирање селекције врши сортирање тако што тражи минимални број и ставља га у прву или последњу позицију према редоследу (узлазно или силазно). Процес претраживања минималног кључа и стављања у одговарајући положај се наставља све док сви елементи не буду постављени на право мјесто.
Рад сортирања сортирања
- Претпоставимо да је низ АРР са Н елемената у меморији.
- У првом проласку, претражује се најмањи кључ заједно са његовим положајем, а затим се АРР [ПОС] замењује АРР-ом [0]. Због тога је АРР [0] сортиран.
- У другом пролазу, поново се одређује положај најмање вредности у подоснову Н-1 елемената. Замените АРР [ПОС] са АРР [1].
- У пролазу Н-1, исти процес се изводи за сортирање Н броја елемената.
Пример:
Кључне разлике између сортирања и сортирања уметања
- Сортирање уметања обично изводи операцију уметања. Напротив, сортна селекција врши избор и позиционирање потребних елемената.
- За сортирање инсертије се каже да је стабилна док сортирање није стабилан алгоритам.
- У алгоритму сортирања уметака елементи су претходно познати. Насупрот томе, сортна селекција садржи претходну локацију.
- Инсертион сортирање је техника сортирања уживо, при чему се долазни елементи одмах сортирају по листи, док сортна селекција не може добро радити са тренутним подацима.
- Сортирање уметања има време трајања О (н) у најбољем случају. Насупрот томе, најбоља сложеност одабраног типа одабира је О (н2).
Сложеност врсте убацивања
Најбоља сложеност уноса је О (н) пута, тј. Када је низ претходно сортиран. На исти начин, када је низ сортиран обрнутим редоследом, први елемент несортираног низа треба упоредити са сваким елементом у сортираном скупу. Дакле, у најгорем случају, време извођења сортирања Инсертион је квадратно, тј. О (н2) . У просечном случају такође мора извршити минимално (к-1) / 2 поређења. Дакле, просјечни случај има и квадратно вријеме рада О (н2).
Сложеност сортирања
Као рад селекције, сортирање не зависи од првобитног реда елемената у низу, тако да не постоји велика разлика између најбољег случаја и најгорег слога селекције.
Сортирање селектује елемент минималне вредности, у процесу селекције се скенира 'н' број елемената; стога се у првом пролазу врши н-1 поређења. Затим се елементи замјењују. Слично томе, у другом пролазу да би се пронашао други најмањи елемент, потребно је скенирање осталих н-1 елемената и процес се наставља све док се цијели низ не сортира.
Према томе, сложеност одабраног сортирања је О (н2) .
= (н-1) + (н-2) + ……… .. + 2 + 1
= н (н-1) / 2 = О (н2)
Закључак
Међу оба алгоритма за сортирање, сортирање је брзо, ефикасно и стабилно, док сортна селекција функционише ефикасно само када је укључен мали скуп елемената или је листа делимично сортирана. Број поређења направљених селекционом сортом је већи од покрета који се изводе, док је код сортирања уметања број пута који је елемент померан или замењен већи од упоређивања.
