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

## Sunday, 1. March 2009

### Testing Quicksort with NaturalSpec

Filed under: F#,NaturalSpec — Steffen Forkmann at 11:42 Uhr

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.

Tags: , ,