sortowanie przez kopcowanie

In computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that heap, placing it at the end of the array in a similar manner to Selection sort.

Key facts

Algorithm.caption: A run of heapsort sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.
Algorithm.data: Array
Algorithm.time: O(n\log n)
Algorithm.average time: O(n\log n)
Algorithm.best time: O(n\log n) (distinct keys)or O(n) (equal keys)
Algorithm.space: O(n) total O(1) auxiliary
Algorithm.class: Sorting algorithm
Algorithm.image: File:Sorting heapsort anim.gif

via Wikipedia infobox

Wikidata facts

Instance of: comparison sort
Image: Binary heap bottomup vs topdown.svg

Show 5 more facts

maintained by WikiProject: WikiProject Mathematics
derivative work: smoothsort
time of discovery or invention: 1964-00-00
Commons category: Heap sort
uses: array data structure

Sources (2)

via Wikidata · CC0

Article · Polski

Sortowanie przez kopcowanie (ang. heapsort), zwane również sortowaniem stogowym – jeden z algorytmów sortowania, choć niestabilny, to jednak szybki i niepochłaniający wiele pamięci (złożoność czasowa wynosi a pamięciowa – przy czym jest to rozmiar sortowanych danych, złożoność pamięciowa dodatkowych struktur wynosi jest to zatem algorytm sortowania w miejscu). Jest on w praktyce z reguły nieco wolniejszy od sortowania szybkiego, lecz ma lepszą pesymistyczną złożoność czasową (przez co jest odporny np. na atak za pomocą celowo spreparowanych danych, które spowodowałyby jego znacznie wolniejsze działanie).

Abstract from DBpedia / Wikipedia · CC BY-SA