{"id":741,"date":"2009-03-01T11:42:14","date_gmt":"2009-03-01T10:42:14","guid":{"rendered":"http:\/\/www.navision-blog.de\/2009\/03\/01\/testing-quicksort-with-naturalspec\/"},"modified":"2009-11-08T11:32:38","modified_gmt":"2009-11-08T10:32:38","slug":"testing-quicksort-with-naturalspec","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2009\/03\/01\/testing-quicksort-with-naturalspec\/","title":{"rendered":"Testing Quicksort with NaturalSpec"},"content":{"rendered":"

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

First of all we define a scenario for sorting:<\/p>\n

\/\/\/ predefined sorting scenario\n<\/span>let <\/span>sortingScenario f list =\n  Given list\n    |> When sorting_with f\n    |> It should be sorted\n    |> It should contain_all_elements_from list\n    |> It should contain_no_other_elements_than list<\/pre>\n
\/\/\/ predefined Quicksort scenario\n<\/span>let <\/span>quicksortScenario list = sortingScenario QuickSort list<\/pre>\n
Now we define some concrete test cases:<\/p>\n
[<Scenario>]\nlet <\/span>When_sorting_empty_list() =\n  quicksortScenario []\n    |> Verify\n    \n[<Scenario>]\nlet <\/span>When_sorting_small_list() =\n  quicksortScenario [2;1;8;15;5;22]\n    |> Verify      \n    \n[<ScenarioTemplate(100)>]\n[<ScenarioTemplate(1000)>]\n[<ScenarioTemplate(2500)>]\nlet <\/span>When_sorting_ordered_list n =\n  quicksortScenario [1..n]\n    |> Verify  \n    \n[<ScenarioTemplate(100)>]\n[<ScenarioTemplate(1000)>]\n[<ScenarioTemplate(2500)>]\nlet <\/span>When_sorting_random_list n =\n  quicksortScenario (list_of_random_ints n)\n    |> Verify  <\/pre>\n
After we defined our spec the task is now to implement the sorting function. I am using a very short (and very na\u00efve) Quicksort implementation in F#:<\/p>\n
\/\/\/ naive implementation of QuickSort - don't use it\n<\/span>let rec <\/span>quicksort = function\n  <\/span>| [] -> <\/span>[]\n  | pivot :: rest ->\n     let <\/span>small,big = List.partition ((>) pivot) rest\n     quicksort small @ [pivot] @ quicksort big\n     \nlet <\/span>QuickSort x =\n  printMethod ""\n  <\/span>quicksort x   <\/pre>\n
If we run the scenario, we get the following output (I shortened a bit):<\/p>\n
\n
Scenario: When sorting empty list <\/p>\n
– Given []
\n    – When sorting with QuickSort
\n    => It should be sorted
\n    => It should contain all elements from []
\n    => It should contain no other elements than []
\n    ==> Result is: []
\n    ==> OK
\n    ==> Time: 0.0355s<\/p>\n
Scenario: When sorting small list<\/p>\n
– Given [2; 1; 8; 15; 5; 22]
\n    – When sorting with QuickSort
\n    => It should be sorted
\n    => It should contain all elements from [2; 1; 8; 15; 5; 22]
\n    => It should contain no other elements than [2; 1; 8; 15; 5; 22]
\n    ==> Result is: [1; 2; 5; 8; 15; 22]
\n    ==> OK
\n    ==> Time: 0.0065s<\/p>\n
Scenario: When sorting ordered list<\/p>\n
[\u2026]  100 elements
\n    ==> OK
\n    ==> Time: 0.0939s<\/p>\n
Scenario: When sorting ordered list<\/p>\n
[\u2026]  1000 elements
\n    ==> OK
\n    ==> Time: 0.7130s<\/p>\n
Scenario: When sorting ordered list<\/p>\n
[\u2026]  2500 elements
\n    ==> OK
\n    ==> Time: 3.0631s<\/p>\n
Scenario: When sorting random list <\/p>\n
[\u2026]  100 elements
\n    ==> OK
\n    ==> Time: 0.0485s<\/p>\n
Scenario: When sorting random list<\/p>\n
[\u2026]  1000 elements
\n    ==> OK
\n    ==> Time: 0.1878s<\/p>\n
Scenario: When sorting random list<\/p>\n
[\u2026]  1000 elements
\n    ==> OK
\n    ==> Time: 0.8713s<\/p>\n<\/blockquote>\n
As you can see the function is much faster if we sort a random list. This is because of the na\u00efve choice of the pivot element.<\/p>\n
I don\u2019t want to give better implementations here (use LINQ<\/a> or PLINQ<\/a>). I just wanted to show how we can easily verify a test function with NaturalSpec.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 |> […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[448,524],"tags":[664,666,539],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/741"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=741"}],"version-history":[{"count":6,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/741\/revisions"}],"predecessor-version":[{"id":922,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/741\/revisions\/922"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=741"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=741"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=741"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}