×

heapsort

swMATH ID: 34903
Software Authors: Williams JWJ
Description: Algorithm 232 heapsort. wikipedia: In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.[1]. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort. Heapsort was invented by J. W. J. Williams in 1964.[2] This was also the birth of the heap, presented already by Williams as a useful data structure in its own right.[3] In the same year, R. W. Floyd published an improved version that could sort an array in-place, continuing his earlier research into the treesort algorithm
Homepage: https://en.wikipedia.org/wiki/Heapsort
Related Software: Quicksort; MA57; HSL; HSL_MA87; GALAHAD; Algorithm 97; OR-Library; Find; AS 266; Julia; Algorithm 447; LAPACK; SteinLib; Qhull; gmp; k.c; MersenneTwister; Mathematica; DQP; HSL_MA77
Referenced in: 61 Publications
all top 5

Referenced by 97 Authors

8 Katajainen, Jyrki
6 Elmasry, Amr
3 Edelkamp, Stefan
3 Gould, Nicholas Ian Mark
3 Letchford, Adam N.
3 Vahrenhold, Jan
2 Carlsson, Svante
2 Fagerberg, Rolf
2 Jensen, Claus
2 Munro, J. Ian
2 Sack, Jörg-Rüdiger
1 Akar, Mehmet
1 Bernstein, Daniel Julius
1 Bille, Philip
1 Blunck, Henrik
1 Boyar, Joan F.
1 Brass, Peter
1 Brazil, Marcus N.
1 Brönnimann, Hervé
1 Browne, Philip A.
1 Buchbinder, Niv
1 Budd, Christopher John
1 Chen, Jingsen
1 Chen, Pin-Liang
1 Cihan, Onur
1 Dijkstra, Edsger Wybe
1 Ding, Yuzheng
1 Doberkat, Ernst-Erich
1 Du, Min-Wen
1 Dutton, Ronald D.
1 Erkan, Ö. Feyza
1 Fredman, Michael L.
1 Gajdoš, Jozef
1 Gambosi, Giorgio
1 Gamby, Ask Neve
1 Geffert, Viliam
1 Gonzalez, Teofilo F.
1 Gørtz, Inge Li
1 Guénoche, E.
1 Gutin, Gregory Z.
1 Han, Wook-Shin
1 Hansen, Pierre
1 Hasham, Alnoor
1 Hsieh, Sun-Yuan
1 Iacono, John
1 Jaumard, Brigitte
1 Johnson, Donald B.
1 Kaparis, Konstantinos
1 Khoong, C. M.
1 Kim, H. Alicia
1 Kim, Jinha
1 Kim, Sungchul
1 Klein, Shmuel Tomi
1 Lange, Kenneth L.
1 Larsen, Kim Skak
1 Lee, Chia-Wei
1 Mattsson, Christer
1 Miller, Sebastian J.
1 Minoux, Michel Andre
1 Moffat, Alistair
1 Morin, Pat
1 Morrison, Jason
1 Nardelli, Enrico
1 Navarro, Gonzalo
1 Oh, Jinoh
1 Pacheco, Joaquín A.
1 Paessens, H.
1 Paredes, Rodrigo
1 Paul, Gerald
1 Paulik, Augustin
1 Pearson, Nicholas A.
1 Petrank, Erez
1 Piotrów, Marek
1 Ras, Charl J.
1 Robinson, Daniel P.
1 Sedgewick, Robert
1 Sevcik, Carlos
1 Skjoldjensen, Frederik Rye
1 Srikanthan, Thambipillai
1 Stølting Brodal, Gerth
1 Strothotte, Thomas W.
1 Suwanda, Hendra
1 Takaoka, Tadao
1 Talamo, Maurizio
1 Tarjan, Robert Endre
1 Thomas, Doreen Anne
1 Toint, Philippe L.
1 Toussaint, Godfried T.
1 Valencia, Olga
1 van Gasteren, Antonetta Johanna Maria
1 Volz, Marcus
1 Wang, Guojin
1 Weiss, Mark Allen
1 Wu, Jigang
1 Xin, Shiqing
1 Yeo, Anders
1 Yu, Hwanjo

Referencing Publications by Year