Below table gives a quick idea of running times, number of comparisions and swaps in various sorting algorithms. For insertion sort rather than swaps they can be considered as moves. Will update the table with linked list, stack and queue operation details.
Algorithm
|
Best
|
Worst
|
Average
|
Comparisons
|
Swaps
|
||
Min
|
Max
|
Min
|
Max
|
||||
Bubble
|
Ω(n2)
|
Θ(n2)
|
Ο(n2)
|
n(n-)/2
|
n(n-)/2
|
0
|
n(n-)/2
|
Selection
|
Ω(n2)
|
Θ(n2)
|
Ο(n2)
|
n(n-)/2
|
n(n-)/2
|
0
|
(n-1)
|
Insertion
|
Ω(n)
|
Θ(n2)
|
Ο(n2)
|
n(n-)/2
|
(n-1)
|
0
|
n(n-)/2
|
Quick
|
Θ(nlogn)
|
Θ(nlogn)
|
Ο(n2)
|
||||
Merge
|
Θ(nlogn)
|
No comments:
Post a Comment