Rash thoughts about .NET, C#, F# and Dynamics NAV.

In my last article I showed two ways to use parameterized scenarios in NaturalSpec. This time I will show how we can combine both to test a small Quicksort function.

First of all we define a scenario for sorting:

/// predefined sorting scenario
let sortingScenario f list =
  Given list
    |> When sorting_with f
    |> It should be sorted
    |> It should contain_all_elements_from list
    |> It should contain_no_other_elements_than list

/// predefined Quicksort scenario
let quicksortScenario list = sortingScenario QuickSort list

Now we define some concrete test cases:

[<Scenario>]
let When_sorting_empty_list() =
  quicksortScenario []
    |> Verify
    
[<Scenario>]
let When_sorting_small_list() =
  quicksortScenario [2;1;8;15;5;22]
    |> Verify      
    
[<ScenarioTemplate(100)>]
[<ScenarioTemplate(1000)>]
[<ScenarioTemplate(2500)>]
let When_sorting_ordered_list n =
  quicksortScenario [1..n]
    |> Verify  
    
[<ScenarioTemplate(100)>]
[<ScenarioTemplate(1000)>]
[<ScenarioTemplate(2500)>]
let When_sorting_random_list n =
  quicksortScenario (list_of_random_ints n)
    |> Verify  

After we defined our spec the task is now to implement the sorting function. I am using a very short (and very naïve) Quicksort implementation in F#:

/// naive implementation of QuickSort - don't use it
let rec quicksort = function
  | [] -> []
  | pivot :: rest ->
     let small,big = List.partition ((>) pivot) rest
     quicksort small @ [pivot] @ quicksort big
     
let QuickSort x =
  printMethod ""
  quicksort x   

If we run the scenario, we get the following output (I shortened a bit):

Scenario: When sorting empty list

– Given []
– When sorting with QuickSort
=> It should be sorted
=> It should contain all elements from []
=> It should contain no other elements than []
==> Result is: []
==> OK
==> Time: 0.0355s

Scenario: When sorting small list

– Given [2; 1; 8; 15; 5; 22]
– When sorting with QuickSort
=> It should be sorted
=> It should contain all elements from [2; 1; 8; 15; 5; 22]
=> It should contain no other elements than [2; 1; 8; 15; 5; 22]
==> Result is: [1; 2; 5; 8; 15; 22]
==> OK
==> Time: 0.0065s

Scenario: When sorting ordered list

[…]  100 elements
==> OK
==> Time: 0.0939s

Scenario: When sorting ordered list

[…]  1000 elements
==> OK
==> Time: 0.7130s

Scenario: When sorting ordered list

[…]  2500 elements
==> OK
==> Time: 3.0631s

Scenario: When sorting random list

[…]  100 elements
==> OK
==> Time: 0.0485s

Scenario: When sorting random list

[…]  1000 elements
==> OK
==> Time: 0.1878s

Scenario: When sorting random list

[…]  1000 elements
==> OK
==> Time: 0.8713s

As you can see the function is much faster if we sort a random list. This is because of the naïve choice of the pivot element.

I don’t want to give better implementations here (use LINQ or PLINQ). I just wanted to show how we can easily verify a test function with NaturalSpec.