Сортирање уз помоћ бинарног стабла

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

Сортирање стаблом је алгоритам за сортирање који гради бинарно стабло претраге од елемената, и онда пролази кроз стабло ("in-order” проласком) тако да елементи на крају испадну сортирани. Највише се употребљава за сортирање елемената приликом тока из неке датотеке. Неколико других алгоритама сортирања би морало да учита елементе у неку привремену структуру, док код сортирања стаблом учитавање у структуру података већ сортира елементе.

Ефикасност[уреди]

Додавање једног елемента у бинарно стабло претраге је у просеку O(log(n)) процес, тако да додавање n елемената чини O(n log(n)) процес, чинећи тако сортирање уз помоћ стабла претраге такозвани 'алгоритам за брзо сортирање'. Али за додавање једног елемента у небалансирано бинарно стабло потребно је O(n) времена у најгорем случају, када стабло подсећа на повезану листу (дегенерисано стабло), чинећи тако овај алгоритам сложености O(n2) у најгорем случају. Најгори случај се покреће када се “сортирању стаблом” предају већ сортирани елементи. Ово би учинило да је време потребно за “убацивање” у бинарно стабло O(n2). Доминантни део алгоритма је “убацивање” у бинарно стабло, претпостављајући да је време за уклањање елемената O(n).

Понашање најогрег случаја се може побољшати користећи само-балансирајуће бинарно стабло претраге. Користећи такво стабло алгоритам постаје сложености O(n log(n)) у најгорем случају и тако постаје оптималан.

Пример[уреди]

Следећи псеудокод алгоритма за сортирање уз помоћ бинарног стабла прима низ упоредивих објеката(елемената) и штампа их у растућем поретку:

STRUCTURE BinaryTree
    BinaryTree:LeftSubTree
    Object:Node
    BinaryTree:RightSubTree
END STRUCTURE
 
PROCEDURE Insert(BinaryTree:searchTree, Object:item)
    IF searchTree IS NULL THEN
        SET searchTree.Node TO item
    ELSE
        IF item IS LESS THAN searchTree.Node THEN
            Insert(searchTree.LeftSubTree, item)
        ELSE
            Insert(searchTree.RightSubTree, item)
        END IF
    END IF
END PROCEDURE
 
PROCEDURE InOrder(BinaryTree:searchTree)
    IF searchTree IS NULL THEN
        EXIT PROCEDURE
    ELSE
        InOrder(searchTree.LeftSubTree)
        PRINT searchTree.Node
        InOrder(searchTree.RightSubTree)
    END IF
END PROCEDURE
 
PROCEDURE TreeSort(Array:items)
    BinaryTree:searchTree
 
    FOR EACH individualItem IN items
        Insert(searchTree, individualItem)
    END FOR
 
    InOrder(searchTree)
END PROCEDURE

У једноставној форми функционалног програмирања алгоритам (у Haskell језику) би изгледао нешто слично следећем коду:

data Tree a = Leaf | Node (Tree a) a (Tree a)
 
insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x (Node t y s) | x <= y = Node (insert x t) y s
insert x (Node t y s) | x > y = Node t y (insert x s)
 
flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node t x s) = flatten t ++ [x] ++ flatten s
 
treesort :: Ord a => [a] -> [a]
treesort = flatten . foldеr insert Leaf

Треба напоменути да у примеру изнад, алгоритам уметања и уклањања елемената оба имају временску сложеност O(n2) у најгорем случају.

Референце[уреди]

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

Шаблон:Сортирање