Coding Katas: Insertion Sort

Datetime:2016-08-23 03:11:46          Topic:          Share

Writing tests for sorting algorithms are interesting. The main issue is that the tests would be the same regardless of which algorithm you chose:

  1. Given [1], sort returns [1]
  2. Given [1,2], sort returns [1,2]
  3. Given [2,1], sort returns [1,2]
  4. Given [1,2,3], sort returns [1,2,3]
  5. Given [2,1,3], sort returns [1,2,3]

In Test Driven Development, when writing code for a test, you are supposed to write the least amount of code necessary to make the current test pass. So if you are going to write algorithms for sorts. All sorting would be the same process:

To resolve the first and second tests all you need to return is the array given.

To resolve the third test, you can check if the first element in the array is bigger than the second, if it is, reverse the array, and return that, otherwise, return the array.

To answer the fifth test, you write the whole damned sorting solution. Whether you’re solving insertion sort, binary sort or quick sort — it doesn’t matter.

Since I wanted to write tests for sorting algorithms I decided that the best way is to think about the solution and incorporate that into my tests.

Insertion sort does what you would typically do if you have a hand of cards. You go from the beginning, each consecutive card that is out of order, you take out of your hand and place in the right spot.

So I built my tests for insertion sort to solve finding the correct spot for a new value in an array first, then implementing the sort was trivial.

Writing this in JavaScript meant that the insertion did not require moving each element over one in the array as it would in a language like Java. Once you have the position, you can remove the element from the array and put it back right where it goes.

Here are the tests I built. You can use my tests for insertion sort , or peruse my solution for insertion sort .

  1. New insertion search init
  2. When 1 is given, getPositionForNewVal returns 0
  3. When 2 is given to 3,4, getPositionForNewVal returns 0
  4. When 3 is given to 2,7,4, getPositionForNewVal returns 1
  5. When 3,2,5,4,7,4 is given, sort returns 2,3,4,4,5,7
  6. When [8682,2602,5961,4659,432,8230,111,3921,2841,5913,4876,800,6748,5720,4660,327,2305,3571,9919,8277,6168,2305,3359,9292,7043] is given, sort returns [111,327,432,800,2305,2305,2602,2841,3359,3571,3921,4659,4660,4876,5720,5913,5961,6168,6748,7043,8230,8277,8682,9292,9919]