Friday, October 26, 2012

Worst Case Best Case and Average Case of Algortihms

Over here we will have a look at algorithms and cases which are required for us to understand it. it is basically the performance of the algortihms kindly go through it

for further clarification u may go to wikipedia links given in this table

NameBestAverageWorstMemoryStableMethodOther notes
Quicksort\mathcal{} n \log n\mathcal{} n \log n\mathcal{} n^2\mathcal{} \log nDependsPartitioningQuicksort is usually done in place with O(log(n)) stack space.[citation needed] Most implementations are unstable, as stable in-place partitioning is more complex. Naïve variants use an O(n) space array to store the partition.[citation needed]
Merge sort\mathcal{} {n \log n} \mathcal{} {n \log n} \mathcal{} {n \log n} Depends; worst case is \mathcal{} n YesMergingHighly parallelizable (up to O(log(n))) for processing large amounts of data.
 Merge sort \mathcal{} - \mathcal{} - \mathcal{} {n \left( \log n \right)^2} \mathcal{} {1} YesMergingImplemented in Standard Template Library (STL);[2] can be implemented as a stable sort based on stable in-place merging.[3]
Heapsort\mathcal{} {n \log n} \mathcal{} {n \log n} \mathcal{} {n \log n} \mathcal{} {1} NoSelection
Insertion sort \mathcal{} n \mathcal{} n^2 \mathcal{} n^2 \mathcal{} {1} YesInsertionO(n + d), where d is the number of inversions
Introsort\mathcal{} n \log n\mathcal{} n \log n\mathcal{} n \log n\mathcal{} \log nNoPartitioning & SelectionUsed in SGI STL implementations
Selection sort \mathcal{} n^2 \mathcal{} n^2 \mathcal{} n^2 \mathcal{} {1} NoSelectionStable with O(n) extra space, for example using lists.[4] Used to sort this table in Safari or other Webkit web browser.[5]
Timsort \mathcal{} {n} \mathcal{} {n \log n} \mathcal{} {n \log n} \mathcal{} n YesInsertion & Merging\mathcal{} {n} comparisons when the data is already sorted or reverse sorted.
Shell sort\mathcal{} n\mathcal{} n (\log n)^2

or

\mathcal{} n^{3/2}		Depends on gap sequence; best known is \mathcal{} n (\log n)^2\mathcal{} 1NoInsertion
Bubble sort\mathcal{} n\mathcal{} n^2\mathcal{} n^2\mathcal{} {1}YesExchangingTiny code size
Binary tree sort\mathcal{} n\mathcal{} {n \log n} \mathcal{} {n \log n} \mathcal{} n YesInsertionWhen using a self-balancing binary search tree
Cycle sort— \mathcal{} n^2 \mathcal{} n^2 \mathcal{} {1} NoInsertionIn-place with theoretically optimal number of writes
Library sort— \mathcal{} {n \log n} \mathcal{} n^2 \mathcal{} n YesInsertion
Patience sorting——\mathcal{} n \log n\mathcal{} nNoInsertion & SelectionFinds all the longest increasing subsequences within O(n log n)
Smoothsort\mathcal{} {n} \mathcal{} {n \log n} \mathcal{} {n \log n} \mathcal{} {1} NoSelectionAn adaptive sort - \mathcal{} {n} comparisons when the data is already sorted, and 0 swaps.
Strand sort\mathcal{} n \mathcal{} n^2\mathcal{} n^2\mathcal{} nYesSelection
Tournament sort—\mathcal{} n \log n\mathcal{} n \log nSelection
Cocktail sort\mathcal{} n\mathcal{} n^2 \mathcal{} n^2 \mathcal{} {1} YesExchanging
Comb sort\mathcal{} n\mathcal{} n \log n \mathcal{} n^2 \mathcal{} {1} NoExchangingSmall code size
Gnome sort \mathcal{} n \mathcal{} n^2 \mathcal{} n^2 \mathcal{} {1} YesExchangingTiny code size
Bogosort \mathcal{} n \mathcal{} n \cdot n! \mathcal{} {n \cdot n! \to \infty} \mathcal{} {1} NoLuckRandomly permute the array and check if sorted.
[6] \mathcal{} - \mathcal{} n \log n \mathcal{} {n \log n} \mathcal{} {1} Yes



Just go through the Algos in your Book or on wikipedia
Posted by at

1 comment:

Thanks For your Valuable Comments

Subscribe to: Post Comments (Atom)