Sorting algorithms: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
== Definition == | |||
'''Stable''' sort: two elements with equal keys are in the same order after sorting. For instance, insertion sort, merge sort, bubble sort are stable. Quicksort, heapsort are '''unstable'''. | |||
== Complexity == | |||
{| class="wikitable" | {| class="wikitable" | ||
!Sorting algoritm | !Sorting algoritm | ||
| Line 25: | Line 29: | ||
|} | |} | ||
== | == Resources == | ||
Revision as of 06:54, 3 June 2018
Definition
Stable sort: two elements with equal keys are in the same order after sorting. For instance, insertion sort, merge sort, bubble sort are stable. Quicksort, heapsort are unstable.
Complexity
| Sorting algoritm | Worst-case performance | Best-case performance | Average performance | Worst-case space complexity |
|---|---|---|---|---|
| Bubblesort | O(n2) | O(n) | O(n2) | O(1) |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) / O(1) with linked list |
| Quicksort | O(n2) | O(n log n) | O(n log n) | O(n) / O(1) with linked list |