Insertion Sort

Insertion Sort has the following properties:

  • It works by moving elements one at a time
  • Works really well for small data sets
  • Consider going with this when the input data may already be sorted or partially sorted
    • The may not have to move the elements around, thereby saving precious cycles
  • Stable sort
    • Keeps the original order of elements with equal values

Testing Notes

  • Had a very interesting time testing my code. I knew that swapping takes time. std::swap takes particularly longer. I disabled that from the beginning itself
  • Even more interesting was how I thought of fixing my code which was running slowly
  • Initially even running an array of size 1K was taking about 4s so I just made a minor change to remove insertIndex ; altogether and do the calculation in the previous line itself. That did the trick. Otherwise the code was taking hours and hours for 1M array size so I had to stop running it.
  • I even tried improving the code a bit futher by ensuring that I do not call insertIndex-1 many a times but that didn’t really help – in fact made it worse again
  • Sorted runs will run much faster because there’s no work to be done in those cases
    • Would be a nice algo to use if your data is mostly sorted

Code

As usual the code is available here:

https://github.com/abhi1010/Algorithms

Numbers

# of Items in Array Time Taken Average for 100 numbers
Random 10 0.006095 0.06095
1K 0.369859 0.0369859
1M 323.878 0.0323878
Sorted 10 0.005022 0.05022
1K 0.11696 0.011696
1M 122.427 0.0122427
Advertisements

One thought on “Insertion Sort

  1. Pingback: Heap Sort vs Merge Sort vs Insertion Sort vs Radix Sort vs Counting Sort vs Quick Sort |

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s