StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The two main theoretical features of sorting algorithms are time complexity and space complexity. </p> <p>In general, <a href="http://en.wikipedia.org/wiki/Time_complexity" rel="noreferrer">time complexity</a> lets us know how the performance of the algorithm changes as the size of the data set increases. Things to consider:</p> <ul> <li><strong>How much data are you expecting to sort?</strong> This will help you know whether you need to look for an algorithm with a very low time complexity.</li> <li><strong>How sorted will your data be already?</strong> Will it be partly sorted? Randomly sorted? This can affect the time complexity of the sorting algorithm. Most algorithms will have worst and best cases - you want to make sure you're not using an algorithm on a worst-case data set.</li> <li><strong>Time complexity is not the same as running time.</strong> Remember that time complexity only describes how the performance of an algorithm varies as the size of the data set increases. An algorithm that always does one pass over all the input would be O(n) - it's performance is linearly correlated with the size of the input. But, an algorithm that always does two passes over the data set is also O(n) - the correlation is still linear, even if the constant (and actual running time) is different. </li> </ul> <p>Similarly, space complexity describes how much space an algorithm needs to run. For example, a simple sort such as <a href="http://en.wikipedia.org/wiki/Insertion_sort" rel="noreferrer">insertion sort</a> needs an additional fixed amount of space to store the value of the element currently being inserted. This is an auxiliary space complexity of O(1) - it doesn't change with the size of the input. However, <a href="http://en.wikipedia.org/wiki/Merge_sort" rel="noreferrer">merge sort</a> creates extra arrays in memory while it runs, with an auxiliary space complexity of O(n). This means the amount of extra space it requires is linearly correlated with the size of the input.</p> <p>Of course, algorithm design is often a trade-off between time and space - algorithms with a low space complexity may require more time, and algoithms with a low time complexity may require more space.</p> <p>For more information, you may find <a href="http://www.leda-tutorial.org/en/official/ch02s02s03.html" rel="noreferrer">this tutorial</a> useful.</p> <hr> <p>To answer your updated question, you may find the wikipedia page on <a href="http://en.wikipedia.org/wiki/Heap_Sort" rel="noreferrer">Heap Sort</a> useful. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload