Sorting algorithms: Difference between revisions
Jump to navigation
Jump to search
Created page with "== References ==" |
No edit summary |
||
| (6 intermediate revisions by the same user not shown) | |||
| 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. Quick sort, heap sort are '''unstable'''. | |||
== Complexity == | |||
{| class="wikitable" | |||
!Sorting algoritm | |||
!Worst-case performance | |||
!Best-case performance | |||
!Average performance | |||
!Worst-case space complexity | |||
|- | |||
|Bubble sort | |||
|O(n<sup>2</sup>) | |||
|O(n) | |||
|O(n<sup>2</sup>) | |||
|O(1) | |||
|- | |||
|Merge sort | |||
|O(n log n) | |||
|O(n log n) | |||
|O(n log n) | |||
|O(n) / O(1) with linked list | |||
|- | |||
|Quick sort | |||
|O(n<sup>2</sup>) | |||
|O(n log n) | |||
|O(n log n) | |||
|O(n) / O(1) with linked list | |||
|- | |||
|Radix sort | |||
| | |||
| | |||
|O(kn) | |||
| | |||
|} | |||
== Resources == | |||
Latest revision as of 07:07, 3 October 2020
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. Quick sort, heap sort are unstable.
Complexity
| Sorting algoritm | Worst-case performance | Best-case performance | Average performance | Worst-case space complexity |
|---|---|---|---|---|
| Bubble sort | O(n2) | O(n) | O(n2) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) / O(1) with linked list |
| Quick sort | O(n2) | O(n log n) | O(n log n) | O(n) / O(1) with linked list |
| Radix sort | O(kn) |