Answers to: How to choose the best sorting algorithm?https://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm<p>I have three implemented sorting algorithm:-</p>
<ol>
<li>Bubble Sort </li>
<li>Merge Sort </li>
<li>Quick Sort</li>
</ol>
<p>How do I select the averagely fastest sorting algorithm based on the characteristics of the given sequence and return the sorted one.</p>enWed, 21 Jan 2015 05:52:43 +0000Comment by codebazz on 0605002's answerhttps://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm#523<p>but vaiya, I think you have missed another thing that is if the array is reversely sorted Quick sort may be not perform best and obviously bubble will be the worst for reversely sorted array. Then I think I should select the merge sort for reversely sorted large array. @Sufian Latif vaiya.</p>codebazzWed, 21 Jan 2015 05:52:43 +0000https://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm#523Answer by 0605002https://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm/521<p>Considering the average case time complexities of the mentioned algorithms, bubble sort is the worst, <code>O(n^2)</code>, and both quicksort and merge sort are <code>O(n lg n)</code>. When sorting data of small sizes you may not notice any difference among these three, but for large arrays bubble sort is no good. So you can scratch it off the list.</p>
<p>Now, while both quicksort and merge sort have the same time complexity, their performance may be different depending on the data. Doing a a merge sort on different data of the same size would require exactly the same number of operations every time. But the number of operations can vary in quicksort. If the data is already sorted, the traditional quicksort would require <code>O(n^2)</code> operations. There is a variation of quicksort, which is called 'randomized quicksort', performs better in such cases. But for sorted data, bubble sort becomes <code>O(n)</code> (because there would be nothing to do).</p>
<p>So, in average case, both quicksort and merge sort have the same time complexity, but in worst case, quicksort and bubble sort can have the same complexity.</p>
<pre><code>Algorithm Best case Average case Worst case
Bubble sort O(n^2) O(n^2) O(n^2)
Quicksort O(n lg n) O(n lg n) O(n^2)
Merge sort O(n lg n) O(n lg n) O(n lg n)
</code></pre>
<p>For a quick look on complexities of algorithms, you can see <a href="http://bigocheatsheet.com/">this</a>.</p>0605002Wed, 21 Jan 2015 05:20:46 +0000https://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm/521Comment by codebazz on Shadek's answerhttps://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm#518<p>but I have only three options: - bubble, merge, quick sort</p>codebazzWed, 21 Jan 2015 03:54:05 +0000https://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm#518Answer by Shadekhttps://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm/516<p>As far as I know, If the input array list is almost sorted insertion sort performs best.</p>ShadekWed, 21 Jan 2015 02:39:07 +0000https://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm/516Answer by Kaiser Ahmedhttps://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm/494<p>You can choose the fastest one by knowing their time complexity (How many time it need to sort n numbers in worst case).The lowest time complexity in worst case is the fastest one.</p>
<p>The fastest algorithm among 3 is Merge sort (Time complexity: n*log(n)). Here you can find all the information about sorting algorithms-<a href="http://en.wikipedia.org/wiki/Sorting_algorithm">Link</a>.</p>Kaiser AhmedTue, 20 Jan 2015 17:15:32 +0000https://programabad.com/questions/489/how-to-choose-the-best-sorting-algorithm/494