Wednesday, April 24, 2013

Best,Worst and average case comparisions for Sorting algorithms


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