Let’s build a Sort method that uses the quicksort algorithm. Note, we’re not trying to use TDD to derive the quicksort algorithm.
Step 1 – test for a null input
Stub the test
[TestFixture]
public class When_asked_to_sort_a_list
{
[Test]
public void Given_null()
{
Test.Verify(
with_a_null_input,
when_asked_to_sort_the_input,
should_throw_an_ArgumentNullException
);
}
public void Sort<T>(IList<T> input)
{
throw new NotImplementedException();
}
}
next fill in the implied details
private Exception _exception;
private List<char> _input;
[SetUp]
public void BeforeEachTest()
{
_input = null;
_exception = null;
}
private void with_a_null_input()
{
_input = null;
}
private void when_asked_to_sort_the_input()
{
try
{
Sort(_input);
}
catch (Exception <span class="hiddenGrammarError" pre="">exception)
{
_exception</span> = exception;
}
}
private void should_throw_an_ArgumentNullException()
{
_exception.ShouldNotBeNull();
_exception.ShouldBeOfType<ArgumentNullException>();
}
run the test
WITH a null input
WHEN asked to sort the input
SHOULD throw an Argument Null Exception - FAILED
then build the necessary implementation.
public void Sort<T>(IList<T> input)
{
if (input == null)
{
throw new ArgumentNullException();
}
throw new NotImplementedException();
}
Step 2 – test for an empty input
Write the test
[Test]
public void Given_an_empty_list()
{
Test.Verify(
with_an_empty_list,
when_asked_to_sort_the_input,
should_not_throw_an_Exception
);
}
private void with_an_empty_list()
{
_input = new List<char>();
}
private void should_not_throw_an_Exception()
{
_exception.ShouldBeNull();
}
run the test
WITH an empty list
WHEN asked to sort the input
SHOULD not throw an Exception - FAILED
FluentAssert.Exceptions.ShouldBeNullAssertionException : Expected: null
But was: System.NotImplementedException: The method or operation is not implemented.
then update the implementation.
public void Sort<T>(IList<T> input)
{
if (input == null)
{
throw new ArgumentNullException();
}
if (!input.Any())
{
return;
}
throw new NotImplementedException();
}
Step 3 – test for a single-element input
[Test]
public void Given_a_single_element_list()
{
Test.Verify(
with_a_list,
that_has_element__A,
when_asked_to_sort_the_input,
should_not_throw_an_Exception,
the_element_of_the_list_should_be__A
);
}
private void with_a_list()
{
with_an_empty_list();
}
private void that_has_element__A()
{
_input.Add('A');
}
private void the_element_of_the_list_should_be__A()
{
_input.ShouldContainAllInOrder(new[] { 'A' });
}
run the test
WITH a list
that has element A - PASSED
WHEN asked to sort the input
SHOULD not throw an Exception - FAILED
FluentAssert.Exceptions.ShouldBeNullAssertionException : Expected: null
But was: System.NotImplementedException: The method or operation is not implemented.
update the implementation.
public void Sort<T>(IList<T> input)
{
if (input == null)
{
throw new ArgumentNullException();
}
if (input.Count <= 1)
{
return;
}
throw new NotImplementedException();
}
Step 4a – test sorting list { A B }
[Test]
public void Given_a_list_with_elements__A_B()
{
Test.Verify(
with_a_list,
that_starts_with_element__A,
followed_by_element__B,
when_asked_to_sort_the_input,
should_not_throw_an_Exception,
the_elements_of_the_sorted_list_should_be__A_B__in_that_order
);
}
private void that_starts_with_element__A()
{
that_has_element__A();
}
private void followed_by_element__B()
{
_input.Add('B');
}
private void the_elements_of_the_sorted_list_should_be__A_B__in_that_order()
{
_input.ShouldContainAllInOrder("AB".ToArray());
}
run the test
WITH a list
that starts with element A - PASSED
followed by element B - PASSED
WHEN asked to sort the input
SHOULD not throw an Exception - FAILED
FluentAssert.Exceptions.ShouldBeNullAssertionException : Expected: null
But was: System.NotImplementedException: The method or operation is not implemented.
update the implementation.
public void Sort<T>(IList<T> input)
{
if (input == null)
{
throw new ArgumentNullException();
}
if (input.Count <= 1)
{
return;
}
}
Step 4b – test sorting list { B A }
[Test]
public void Given_a_list_with_elements__B_A()
{
Test.Verify(
with_a_list,
that_starts_with_element__B,
followed_by_element__A,
when_asked_to_sort_the_input,
should_not_throw_an_Exception,
the_elements_of_the_sorted_list_should_be__A_B__in_that_order
);
}
private void that_has_element__B()
{
_input.Add('B');
}
private void followed_by_element__B()
{
that_has_element__B();
}
private void that_starts_with_element__B()
{
that_has_element__B();
}
private void followed_by_element__A()
{
that_has_element__A();
}
run the test
WITH a list
that starts with element B - PASSED
followed by element A - PASSED
WHEN asked to sort the input
SHOULD not throw an Exception - PASSED
the elements of the sorted list should be A B in that order - FAILED
FluentAssert.Exceptions.ShouldBeEqualAssertionException : at offset 0
update the implementation.
public void Sort<T>(IList<T> input)
where T : IComparable
{
if (input == null)
{
throw new ArgumentNullException();
}
if (input.Count <= 1)
{
return;
}
SwapIfOutOfOrder(input, 0, 1);
}
private static void SwapIfOutOfOrder<T>(IList<T> input, int first, int second)
where T : IComparable
{
if (input[first].CompareTo(input[second]) == 1)
{
var temp = input[first];
input[first] = input[second];
input[second] = temp;
}
}
Step 4c – track comparisons
In order to verify that the sort algorithm used by Sort is quicksort we need the ability to introspect what it is doing. Verifying that the output is sorted is insufficient because it could be using some other sort algorithm and we specifically want to implement quicksort. In a previous post we passed an instrumented IComparer along with the list to the sorted to the Sort method. This time we’ll try something different. We’ll wrap the objects being sorted so that we can count the number of comparisons performed during the sort. This has the advantage of working with any Sort implementation that can sort IComparable elements and with lists that contain duplicate elements.
public class ComparableWrapper<T> : IComparable
where T : IComparable
{
private readonly T _value;
private readonly Action _action;
public ComparableWrapper(T value, Action action)
{
_value = value;
_action = action;
}
public T Value
{
get { return _value; }
}
public int CompareTo(object obj)
{
var otherWrapper = obj as ComparableWrapper<T>;
if (otherWrapper == null)
{
throw new ArgumentException("Object is not a ComparableWrapper");
}
_action();
return _value.CompareTo(otherWrapper._value);
}
}
update the tests to use the wrapper
private List<ComparableWrapper<char>> _input;
private int _comparisonCount;
private void IncrementCount()
{
_comparisonCount++;
}
[SetUp]
public void BeforeEachTest()
{
_comparisonCount = 0;
_input = null;
_exception = null;
}
private void with_an_empty_list()
{
_input = new List<ComparableWrapper<char>>();
}
private void Add(char value)
{
_input.Add(new ComparableWrapper<char>(value, IncrementCount));
}
private void that_has_element__A()
{
Add('A');
}
private void that_has_element__B()
{
Add('B');
}
private void the_element_of_the_list_should_be__A()
{
_input.Select(x => x.Value)
.ShouldContainAllInOrder(new[] {'A'});
}
private void the_elements_of_the_sorted_list_should_be__A_B__in_that_order()
{
_input.Select(x => x.Value)
.ShouldContainAllInOrder("AB".ToArray());
}
and add to the tests to check the comparison count.
[Test]
public void Given_a_list_with_elements__A_B()
{
Test.Verify(
with_a_list,
that_starts_with_element__A,
followed_by_element__B,
when_asked_to_sort_the_input,
should_not_throw_an_Exception,
the_elements_of_the_sorted_list_should_be__A_B__in_that_order,
should_perform_at_most_1_comparison
);
}
private void should_perform_at_most_1_comparison()
{
_comparisonCount.ShouldBeLessThanOrEqualTo(1);
}
[Test]
public void Given_a_list_with_elements__B_A()
{
Test.Verify(
with_a_list,
that_starts_with_element__B,
followed_by_element__A,
when_asked_to_sort_the_input,
should_not_throw_an_Exception,
the_elements_of_the_sorted_list_should_be__A_B__in_that_order,
should_perform_at_most_1_comparison
);
}
Step 5a – test sorting list { C B A }
[Test]
public void Given_a_list_with_elements__C_B_A()
{
Test.Verify(
with_a_list,
that_starts_with_element__C,
followed_by_element__B,
followed_by_element__A,
when_asked_to_sort_the_input,
should_not_throw_an_Exception,
the_elements_of_the_sorted_list_should_be__A_B_C__in_that_order,
should_perform_at_most_3_comparisons
);
}
private void that_starts_with_element__C()
{
that_has_element__C();
}
private void that_has_element__C()
{
Add('C');
}
private void the_elements_of_the_sorted_list_should_be__A_B_C__in_that_order()
{
_input.Select(x => x.Value)
.ShouldContainAllInOrder("ABC".ToArray());
}
private void should_perform_at_most_3_comparisons()
{
_comparisonCount.ShouldBeLessThanOrEqualTo(3);
}
run the test
WITH a list
that starts with element C - PASSED
followed by element B - PASSED
followed by element A - PASSED
WHEN asked to sort the input
SHOULD not throw an Exception - PASSED
the elements of the sorted list should be A B C in that order - FAILED
FluentAssert.Exceptions.ShouldBeEqualAssertionException : at offset 0
update the implementation.
public void Sort<T>(IList<T> input)
where T : IComparable
{
if (input == null)
{
throw new ArgumentNullException();
}
if (input.Count <= 1)
{
return;
}
SwapIfOutOfOrder(input, 0, 1);
if (input.Count == 2)
{
return;
}
SwapIfOutOfOrder(input, 0, 2);
SwapIfOutOfOrder(input, 1, 2);
}
Step 5b – test sorting all permutations of list { C B A }
To make sure the code works for all permutations of the list we’ll make use of the Permute extension and FormatForDisplay extension built in previous postings.
[Test]
public void Should_be_able_to_sort_all_permutations_of__C_B_A__with_at_most_3_comparisons_each()
{
with_a_list();
that_starts_with_element__C();
followed_by_element__B();
followed_by_element__A();
foreach (var permutation in _input.Permute(3))
{
_comparisonCount = 0;
_input = permutation.ToList();
try
{
when_asked_to_sort_the_input();
the_elements_of_the_sorted_list_should_be__A_B_C__in_that_order();
should_perform_at_most_3_comparisons();
}
catch (Exception e)
{
Console.WriteLine("failed on permutation " + permutation.Select(x => x.Value).FormatForDisplay());
throw;
}
}
}
run the test and get an unexpected failure
failed on permutation { C A B }
FluentAssert.Exceptions.ShouldBeEqualAssertionException : at offset 0
due to an assumption made about the values returned by CompareTo. Fix it:
private static void SwapIfOutOfOrder<T>(IList<T> input, int first, int second)
where T : IComparable
{
if (input[first].CompareTo(input[second]) > 0)
{
var temp = input[first];
input[first] = input[second];
input[second] = temp;
}
}
Step 6a – test sorting list { D C A B }
[Test]
public void Given_a_list_with_elements__D_C_A_B()
{
Test.Verify(
with_a_list,
that_starts_with_element__D,
followed_by_element__C,
followed_by_element__A,
followed_by_element__B,
when_asked_to_sort_the_input,
should_not_throw_an_Exception,
the_elements_of_the_sorted_list_should_be__A_B_C_D__in_that_order,
should_perform_at_most_6_comparisons
);
}
private void that_starts_with_element__D()
{
that_has_element__D();
}
private void that_has_element__D()
{
Add('D');
}
private void followed_by_element__C()
{
that_has_element__C();
}
private void the_elements_of_the_sorted_list_should_be__A_B_C_D__in_that_order()
{
_input.Select(x => x.Value)
.ShouldContainAllInOrder("ABCD".ToArray());
}
private void should_perform_at_most_6_comparisons()
{
_comparisonCount.ShouldBeLessThanOrEqualTo(6);
}
run the test
WITH a list
that starts with element D - PASSED
followed by element C - PASSED
followed by element A - PASSED
followed by element B - PASSED
WHEN asked to sort the input
SHOULD not throw an Exception - PASSED
the elements of the sorted list should be A B C D in that order - FAILED
FluentAssert.Exceptions.ShouldBeEqualAssertionException : at offset 0
update the implementation to use bubble sort.
public void Sort<T>(IList<T> input) where T : IComparable
{
if (input == null)
{
throw new ArgumentNullException();
}
for (int outer = input.Count; outer >= 1; outer--)
{
for (int inner = 0; inner < outer - 1; inner++)
{
SwapIfOutOfOrder(input, inner, inner + 1);
}
}
}
Step 6b – test sorting all permutations of list { D C A B } with at most 6 comparisons each
[Test]
public void Should_be_able_to_sort_all_permutations_of__D_C_A_B__with_at_most_6_comparisons_each()
{
with_a_list();
that_starts_with_element__D();
followed_by_element__C();
followed_by_element__A();
followed_by_element__B();
foreach (var permutation in _input.Permute(4))
{
_comparisonCount = 0;
_input = permutation.ToList();
try
{
when_asked_to_sort_the_input();
the_elements_of_the_sorted_list_should_be__A_B_C_D__in_that_order();
should_perform_at_most_6_comparisons();
}
catch (Exception e)
{
Console.WriteLine("failed on permutation " + permutation.Select(x => x.Value).FormatForDisplay());
throw;
}
}
}
test passes.
Step 6c – test sorting all permutations of list { D C A B } with less than 6 comparisons each on average
This is the where we force the implementation away from bubble sort. Bubble sort always uses 6 comparisons to sort 4 elements but quicksort only needs 6 in the worst case.
[Test]
public void Should_be_able_to_sort_all_permutations_of__D_C_A_B__with_less_than_6_comparisons_each_on_average()
{
with_a_list();
that_starts_with_element__D();
followed_by_element__C();
followed_by_element__A();
followed_by_element__B();
int totalComparisons = 0;
int totalPermutations = 0;
foreach (var permutation in _input.Permute(4))
{
totalPermutations++;
_comparisonCount = 0;
_input = permutation.ToList();
try
{
when_asked_to_sort_the_input();
the_elements_of_the_sorted_list_should_be__A_B_C_D__in_that_order();
should_perform_at_most_6_comparisons();
totalComparisons += _comparisonCount;
}
catch (Exception e)
{
Console.WriteLine("failed on permutation " + permutation.Select(x => x.Value).FormatForDisplay());
throw;
}
}
var average = totalComparisons / (double)totalPermutations;
average.ShouldBeLessThan(6, () => "Incorrect average number of comparisons - " + average);
}
run the test
FluentAssert.Exceptions.ShouldBeLessThanAssertionException : Incorrect average number of comparisons - 6
update the implementation using the wikipedia algorithm as a guide.
public void Sort<T>(IList<T> input)
where T : IComparable
{
if (input == null)
{
throw new ArgumentNullException();
}
var segments = new Stack<int[]>();
segments.Push(new[] { 0, input.Count - 1 });
while (segments.Any())
{
var segment = segments.Pop();
int first = segment[0];
int last = segment[1];
int middle = GetMiddle(first, last);
while (first < last)
{
while (first < middle && AreInCorrectOrder(input, first, middle))
{
first++;
}
while (last > middle && AreInCorrectOrder(input, middle, last))
{
last--;
}
if (first < last)
{
Swap(input, first, last);
first++;
last--;
if (first - 1 == middle)
{
middle = ++last;
}
else if (last + 1 == middle)
{
middle = --first;
}
}
}
if (middle - segment[0] > 1)
{
segments.Push(new[] { segment[0], middle - 1 });
}
if (segment[1] - middle > 1)
{
segments.Push(new[] { middle + 1, segment[1] });
}
}
}
private static int GetMiddle(int first, int last)
{
return first + ((last - first) >> 1);
}
private static bool AreInCorrectOrder<T>(IList<T> input, int first, int second)
where T : IComparable
{
return input[first].CompareTo(input[second]) <= 0;
}
private static void Swap<T>(IList<T> input, int first, int second)
{
var temp = input[first];
input[first] = input[second];
input[second] = temp;
}
Step 7 – make sure the implementation can handle all permutations of list { A B C D E F G H }
[Test]
public void Should_be_able_to_sort_all_permutations_of__A_B_C_D_E_F_G_H()
{
with_a_list();
"ABCDEFGH".ToList().ForEach(Add);
foreach (var permutation in _input.Permute(8))
{
_comparisonCount = 0;
_input = permutation.ToList();
try
{
when_asked_to_sort_the_input();
the_elements_of_the_sorted_list_should_be__A_B_C_D_E_F_G_H_in_that_order();
}
catch (Exception e)
{
Console.WriteLine("failed on permutation " + permutation.Select(x => x.Value).FormatForDisplay());
throw;
}
}
}
private void the_elements_of_the_sorted_list_should_be__A_B_C_D_E_F_G_H_in_that_order()
{
_input.Select(x => x.Value)
.ShouldContainAllInOrder("ABCDEFGH".ToArray());
}
test passes.
Final – how does this implementation compare to List.Sort?
First get the number of comparisons our Sort uses across all permutations of { A B C D E F G H }
var input = "ABCDEFGH"
.Select(x=>new ComparableWrapper<char>(x, IncrementCount))
.ToList();
foreach (var permutation in input.Permute(8))
{
Sort(permutation);
}
Console.WriteLine("total comparisons: "+_comparisonCount);
output
total comparisons: 682272
Now get the number of comparisons List.Sort uses for the same set of inputs.
var input = "ABCDEFGH"
.Select(x=>new ComparableWrapper<char>(x, IncrementCount))
.ToList();
foreach (var permutation in input.Permute(8))
{
permutation.ToList().Sort();
}
Console.WriteLine("total comparisons: "+_comparisonCount);
output
total comparisons: 1209888
whoa! Our no-frills implementation of quicksort uses only 56% of the comparisons that List.Sort requires to achieve the same goal!
682272 / 1209888 = 0.563913354
It kind of makes you wonder: which sort algorithm does List.Sort use?
Read Full Post »
Cℓinton's Blog 