Algoritmos De Comparación
In this table, n is the number of records to be sorted and k is the average length of the keys. The columns "Best", "Average", and "Worst" give the time complexity in eachcase; estimates that do not use k assume k to be constant. "Memory" denotes the amount of auxiliary storage needed beyond that used by the list itself. These are all comparison sorts.
Name |Best|Average |Worst |Memory |Stable |Method |Other notes | |Bubble sort |O(n) |— |O(n2) |O(1) |Yes |Exchanging |Times are for best variant | |Cocktail sort |O(n) |— |O(n2) |O(1) |Yes |Exchanging | | |Combsort |O(nlog n) |O(nlog n) |O(nlog n) |O(1) |No |Exchanging | | |Gnome sort |O(n) |— |O(n2) |O(1) |Yes |Exchanging | | |Selection sort |O(n2) |O(n2) |O(n2) |O(1) |No |Selection | | |Insertion sort|O(n) |— |O(n2) |O(1) |Yes |Insertion | | |Shell sort |— |— |O(n1.5) |O(1) |No |Insertion | | |Binary tree sort |O(nlog(n)) |O(nlog(n)) |O(nlog(n)) |O(n) |Yes |Insertion | | |Library sort |O(n)|O(nlog(n)) |O(n2) |O(n) |Yes |Insertion | | |Merge sort |O(nlog(n)) |O(nlog(n)) |O(nlog(n)) |O(n) |Yes |Merging | | |In-place merge sort |O(nlog(n)) |O(nlog(n)) |O(nlog(n)) |O(1) |Yes |Merging |Times are forbest variant | |Heapsort |O(nlog(n)) |O(nlog(n)) |O(nlog(n)) |O(1) |No |Selection | | |Smoothsort |O(n) |— |O(nlog(n)) |O(1) |No |Selection | | |Quicksort |O(nlog(n)) |O(nlog(n)) |O(n2) |O(log n) |No|Partitioning |Naive variants use O(n) space | |Introsort |O(nlog(n)) |O(nlog(n)) |O(nlog(n)) |O(logn) |No |Hybrid | | |Patience sorting |O(n) |— |O(nlog(n)) |O(n) |No |Insertion |Finds all thelongest increasing subsequences within O(n log log(n)) | |
(This table describes sorting algorithms that are not comparison sorts. As such, they are not limited by a O(nlog(n)) lower bound.Complexities below are in terms of n, the number of items to be sorted, and k, the size of each key.
Name |Best |Average |Worst |Memory |Stable | |Pigeonhole sort |O(n+2k) |O(n+2k) |O(n+2k)...
Regístrate para leer el documento completo.