Comparison of my own Insertion Sort versus the standard algorithm - Software Engineering Stack Exchange most recent 30 from softwareengineering.stackexchange.com 2019-09-23T18:51:45Z https://softwareengineering.stackexchange.com/feeds/question/161998 https://creativecommons.org/licenses/by-sa/4.0/rdf https://softwareengineering.stackexchange.com/q/161998 2 Comparison of my own Insertion Sort versus the standard algorithm Tom https://softwareengineering.stackexchange.com/users/62485 2012-08-23T13:50:54Z 2012-08-23T15:51:00Z <p>I come from a background of making MVC websites and HTML5 applications, and have recently decided to dive into the sort of stuff i wasn't taught at university, namely the things most people would learn on a computer science course.</p> <p>I've been reading a book on algorithms, and the first one it mentions was the Insertion Sort. I didn't really understand it the first time, but I understood the goal, so I had a crack at coming up with my own solution before reading more into the proper solution to see how close I got.</p> <p>I got pretty close, and here is my function in C#:</p> <pre><code> int[] SortNumbersTomsVersion(int[] numbersIn) { int[] output = new int[numbersIn.Count()]; for (var i = 0; i &lt; numbersIn.Count(); i++) { int cardsLowerThan = 0; for (var n = 0; n &lt; numbersIn.Count(); n++) { if (numbersIn[n] &lt; numbersIn[i]) { cardsLowerThan++; } } output[cardsLowerThan] = numbersIn[i]; } return output; } </code></pre> <p>The concept of it is that, i start off with a group of numbers. Then, for each number, I compare it to all of the other numbers in the array, to see how many others are lower in value. It then takes the resulting count, and places the current number into an output array at that index. The algorithm goes through all the numbers until they are all at the same location.</p> <p>My question is, <em>what makes the original better than my solution</em>?</p> <p>for reference, here is the accepted algorithm outside of a function:</p> <pre><code> int temp, k; for (int i = 1; i &lt; array_size; i++) { temp = array[i]; k = i - 1; while (k &gt;= 0 &amp;&amp; array[k] &gt; temp) { array[k + 1] = array[k]; k--; } array[k + 1] = temp; } </code></pre> https://softwareengineering.stackexchange.com/questions/161998/-/161999#161999 5 Answer by NoChance for Comparison of my own Insertion Sort versus the standard algorithm NoChance https://softwareengineering.stackexchange.com/users/34148 2012-08-23T14:03:35Z 2012-08-23T15:51:00Z <p>Comparing performance of 2 algorithms, assuming both work correctly, involves several factors such as space, speed, etc. Without detailed analysis, your code has nested <em>for</em> loops each bound by (n) iterations:</p> <pre><code>for (var i = 0; i &lt; numbersIn.Count(); i++) { ... for (var n = 0; n &lt; numbersIn.Count(); n++) ...}} </code></pre> <p>this calls for O(n*n) even at the best case (when elements are already sorted). The insertion sort algorithm is supposed to be O(n) in the best case see: <a href="http://en.wikipedia.org/wiki/Insertion_sort" rel="nofollow">Wiki-InsertionSort</a>.</p>