Алгоритми сортирања

Из Википедије, слободне енциклопедије

У рачунарству и информатици алгоритам сортирања је процес преуређивања елеманата неког скупа по одређеном поретку. Најчешће се користе нумерички и лексикографски поредак. Сортирање скупа података је предуслов за његово је ефикасно претраживање. Сортирање је такође врло корисно при утврђивању једнакости два скупа података.

За излазни скуп података, тј. резултат сортирања важи да представља пермутацију улазног скупа и да је сваки елемент излазног скупа мањи или једнак претходном елементу по одабраном поретку.

Класификација[уреди]

Подела алгоритама се врши на основу глобалног метода сортирања и чине је две групе:

  • Алгоритми сортирања поређењем
  • Алгоритми сортирања без поређења

Алгоритми сортирања поређењем[уреди]

Код ове групе алгоритама сортирања, елементи улазног скупа се прераспоређују на основу неког кључа. Кључ представља посебно одабрану вредност која одређује да ли је неки елемент већи, мањи или једнак неком другом елементу улазног скупа. Највећи број алгоритама припада овој групи, а они се даље могу класификовати на следећи начин.

  • Алгоритми уметања
  1. Insertion sort
  2. Shell sort
  • Алгоритми избора
  1. Selection sort
  2. Heapsort
  • Алгоритми замене
  1. Bubble sort
  2. Quicksort

Алгоритми сортирања без поређења[уреди]

Ови алгоритми користе друге методе осим поређења кључева елемената да би дошли до жељеног редоследа елемената. Основни разлог за развој ових алгоритама је што алгоритми сортирања поређењем у најбољем случају имају сложеност O(n·log(n)), док алгоритми сортирања без поређења могу достићи линеарну сложеност.

Најзначајнији алгоритми из ове групе су:

  1. Bucket sort
  2. Counting sort
  3. Radix sort

Укратко о познатим алгоритмима сортирања[уреди]

При опису алгоритама користи се константа n која означава број елемената улазног скупа.

Insertion sort[уреди]

Vista-xmag.png За више информација погледајте чланак Insertion sort

Код Insertion sort алгоритма улазни скуп се дели на два подскупа. Први скуп чини само први елемент улазног скупа јер се подразумева да је скуп са једним елементом увек сортиран. Други скуп чине сви остали елементи. У свакој итерацији из неуређеног скупа се бира први елемент и он се убацује на одговарајуће место у уређеном скупу, а сви елементи уређеног скупа који су већи или једнаки од њега се померају за једно место да би му ослободили локацију. Након n-1 итерација улазни скуп је сортиран.

Shell sort[уреди]

Shell sort се другачије назива сортирање са инкрементом h, јер се улазни скуп на почетку дели на h подскупова. Ови подскупови се затим интерно сортирају, а након тога се инкремент смањује. Овако добијени подскупови се поново интерно сортирају и поступак се понавља све док инкремент не постане 1, када је скуп сортиран.

Selection sort[уреди]

Vista-xmag.png За више информација погледајте чланак Сортирање селекцијом
Selection sort

Код Selection sort алгоритма улазни скуп се дели на два подскупа. Први чине несортирани елементи и на почетку је то цео улазни скуп, док други чине сортирани елементи и овај скуп је на почетку празан. Алгоритам у првој итерацији пролази кроз скуп несортираних елемената, проналази највећи елемент и он замени место са последњим елементом. Затим се у другој итерацији налази највећи елемент из несортираног дела и он мења место са претпоследњим елементом. Након пролаза кроз n итерација улазни скуп је сортиран.

Heapsort[уреди]

Heapsort је један од најефикаснијих алгоритама сортирања. Представља побољшање алгоритма сортирања помоћу стабла јер не захтева додатну меморију за чување стабла. За сортирање се користи структура звана хип која представља скоро комплетно бинарно стабло код ког за сваки чвор важи да је његова вредност већа или једнака од вредности оба потомка. У првој фази алгоритма формира се описана структура хипа, а затим се у свакој фази бира највећи елемент са хипа који се налази у корену, а хип се преуређује. Ови кораци се понављају док се хип не испразни, након чега је улазни скуп сортиран.

Quicksort[уреди]

Vista-xmag.png За више информација погледајте чланак Квиксорт

Quicksort алгоритам има три фазе. У првој фази се бира један елемент, такозвани пивот, а затим се два новонастала подскупа улазног скупа лево и десно од пивота преуређују тако да лево остану елементи мањи од пивота, а десно већи од њега. Након овог корака пивот је сигурно на свом месту. Алгоритам затим рекурзивно примењује описану стратегију на два скупа лево и десно од пивота, све док се не добије сортиран низ.

Bubble sort[уреди]

Bubble sort

Bubble sort је прилично неефикасан алгоритам, али се често примењује због своје једноставности. Његов принцип је пролаз кроз улазни скуп више пута, при чему се упоређују два суседна елемента и ако је први већи од другог, они мењају места. Алгоритам се може мало побољшати ако приметимо да су након i-тог проласка i највећих елемената сортирани и да њих не треба даље проверавати.

Bucket sort[уреди]

Bucket sort алгоритам дели улазни скуп елемената у одређен број „кофа“ на основу неке карактеристике. Затим се алгоритам рекурзивно примењује на сваку кофу појединачно све док у кофама не остане по један или ниједан елемент. Након тока се по одређеном поретку обиђу све кофе и елементи сакупе у излазни скуп. Алгоритам је значајан јер при добром начину поделе елемената по кофама даје линеарну сложеност, али ако ова подела није адекватна, сложеност може порасти од чак О(n²).

Counting sort[уреди]

Код Counting sort алгоритма за сваки елемент улазног скупа чува се кључ који може бити у опсегу од 1 до k, при чему је k број различитих вредности у улазном скупу. На основу овог кључа за сваки елемент се рачуна колико има елемената улазног скупа који су мањи или једнаки од њега. Мана овог алгоритма је потреба за додатном меморијом за помоћне структуре података.

Radix sort[уреди]

Radix sort је врло сличан Bucket sort алгоритму јер дели улазни скуп на класе еквиваленције. Код овог алгоритма критеријум поделе је цифра највеће тежине или цифра најмање тежине у кључу. Разлика је што се након сваке итерације алгоритам не примењује рекурзивно на сваку класу, већ поново на све класе еквиваленције. На овај начин на крају само треба обићи класе по реду јер су унутар класа елементи већ сортирани.

Види још[уреди]

Литература[уреди]

  • D. E. Knuth (October 1998). The Art of Computer Programming Volume 3: Sorting and Searching (3rd ed ed.). Addison-Wesley Professional. ISBN 978-0-201-48541-7. 
  • William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling (October 1992). Numerical Recipes in C: The Art of Scientific Computing (Second Edition ed.). Cambridge University Press. ISBN 978-0-521-43108-8. 
  • Thomas H. Cormen (Author), Charles E. Leiserson (Author), Ronald L. Rivest (Author), Clifford Stein (July 2009). Introduction to Algorithms (Third edition ed.). The MIT Press. ISBN 978-0-262-03384-8. 

Спољашње везе[уреди]