Sorting Kata - List Sort

In the setup we created a solution with two projects. The purpose of these two projects was for a Sorting Kata.

In Linq OrderBy we added a Bookshelf class to hold our sorting methods. I'm going to overwrite that code to keep the Kata short.

Now we can add further sorting methods to test. The List class has a built-in sort method. Let's try it out. First we write a failing test against the Bookshelf class ListSort method.

BookSorting.Test/SortingTest.cs
using System.Collections.Generic;
using System.Linq;

using NUnit.Framework;

namespace BookSorting.Test
{
    [TestFixture]
    public class SortingTest
    {
        [Test]
        public void Authors_SortedByLastName()
        {
            var book1 = new Book
                        {
                            Title = "Wait: The Art and Science of Delay",
                            Author = new Author
                                     {
                                         LastName = "Partnoy",
                                         FirstName = "Frank",
                                     },
                        };

            var book2 = new Book
                        {
                            Author = new Author
                                     {
                                         LastName = "Watt",
                                         FirstName = "Andrew",
                                     },
                            Title = "Beginning Regular Expressions",
                        };

            var books = new List<Book>
                        {
                            book1,
                            book2,
                        };

            var bookshelf = new Bookshelf();

            books = bookshelf.ListSort(books);

            Assert.AreEqual(book1, books.First());
        }
    }
}

We use CTRL+. to add the ListSort method that accepts the list of books. Our goal is for the method to return a sorted list. Then we can assert that the correct book appears first.

Running the test causes the following error:

1 test failed: System.NotImplementedException

Hurray, the test failed. We use the Red, Green, Refactor pattern from Kent Beck's book, Test Driven Design By Example.

The problem is, it failed for the wrong reason. We want to see a failure because the books are not sorted. Let's take a look at the Bookshelf class.

BookSorting/Bookshelf.cs
using System.Collections.Generic;

namespace BookSorting
{
    public class Bookshelf
    {
        public List<Book> ListSort(List<Book> books)
        {
            throw new System.NotImplementedException();
        }
    }
}

Well, that explains our "NotImplementedException".

So, what is it going to take to get this test to fail for the right reason? Let's take a look at Uncle Bob's Transformation Priority Premise. The first transformation we should try is "nil". Can we get the test to fail by doing nothing? No, our code will not compile unless we return something. The next step is a constant. Let's just return the books list as is.

BookSorting/Bookshelf.cs
using System.Collections.Generic;

namespace BookSorting
{
    public class Bookshelf
    {
        public List<Book> ListSort(List<Book> books)
        {
            return books;
        }
    }
}

1 test passed

This is why we Red, Green, Refactor. Our test passed when we didn't want it to. Let's flip the order we put the books into the list.

BookSorting.Test/SortingTest.cs
var books = new List<Book>
{
    book2,
    book1,
};

1 test failed Expected: Partnoy, Frank. Wait: The Art and Science of Delay But was: Watt, Andrew. Beginning Regular Expressions

In Linq OrderBy we overrode the Book.ToString() to get the author and title.

We saw a failing test (Red), and we made sure the message was helpful. Now we can make it green.

BookSorting/Bookshelf.cs
using System.Collections.Generic;

namespace BookSorting
{
    public class Bookshelf
    {
        public List<Book> ListSort(List<Book> books)
        {
            books.Sort();

            return books;
        }
    }
}

1 test failed System.InvalidOperationException : Failed to compare two elements in the array.

The List Sort method does not know how to compare two books. We need the Book class to implement IComparable.

BookSorting/Book.cs
using System;

namespace BookSorting
{
    public class Book : IComparable
    {
        public Author Author { get; set; }

        public string Title { get; set; }

        public override string ToString()
        {
            return string.Format(
                "{0}, {1}. {2}",
                Author.LastName,
                Author.FirstName,
                Title);
        }

        public int CompareTo(object obj)
        {
            return -1;
        }
    }
}

1 test failed Expected: Partnoy, Frank. Wait: The Art and Science of Delay But was: Watt, Andrew. Beginning Regular Expressions

Returning -1 causes the test fail for the right reason and gives a helpful message.

Let's try every constant that the CompareTo can return and test it.

Test Results Value Description
Fail -1 Less than zero means this instance of book precedes the compared book in the sort order.
Pass 0 Zero means this instance of book occurs in the same position in the sort order as the compared book.
Pass 1 Greater than zero means this instance of book follows compared book in the sort order.

Returning 0 and 1 causes the test to pass when they should not. Let's update our test so that 0 and 1 also fail.

BookSorting.Test/SortingTest.cs
[Test]
public void Authors_SortedByLastName()
{
    var book1 = new Book
                {
                    Title = "Wait: The Art and Science of Delay",
                    Author = new Author
                                {
                                    LastName = "Partnoy",
                                    FirstName = "Frank",
                                },
                };

    var book2 = new Book
                {
                    Author = new Author
                                {
                                    LastName = "Watt",
                                    FirstName = "Andrew",
                                },
                    Title = "Beginning Regular Expressions",
                };

    var book3 = new Book
                {
                    Author = new Author
                                {
                                    LastName = "Weinberg",
                                    FirstName = "Steven",
                                },
                    Title = "Cosmology",
                };

    var books = new List<Book>
                {
                    book2,
                    book3,
                    book1,
                };

    var bookshelf = new Bookshelf();

    books = bookshelf.ListSort(books);

    Assert.AreEqual(book1, books.First());
    Assert.AreEqual(book3, books.Last());
}

1 test failed Expected: Weinberg, Steven. Cosmology But was: Watt, Andrew. Beginning Regular Expressions

Good, all the possible constant values fail testing. Let's make it green by updating the CompareTo.

BookSorting/Book.cs
public int CompareTo(object obj)
{
    // By convention put the nulls at the beginning of the sort order.
    if (obj == null)
    {
        return 1;
    }

    var comparedBook = obj as Book;

    if (comparedBook == null)
    {
        throw new ArgumentException("Could not sort the object because it is not a book.");
    }

    if (Author == null
        || (Author.LastName.Equals(comparedBook.Author.LastName, StringComparison.OrdinalIgnoreCase)
            && Author.FirstName.Equals(comparedBook.Author.FirstName, StringComparison.OrdinalIgnoreCase)))
    {
        return string.Compare(Title, comparedBook.Title, StringComparison.OrdinalIgnoreCase);
    }

    if (Author.LastName.Equals(comparedBook.Author.LastName, StringComparison.OrdinalIgnoreCase))
    {
        return string.Compare(
            Author.FirstName, comparedBook.Author.FirstName, StringComparison.OrdinalIgnoreCase);
    }

    return string.Compare(Author.LastName, 
        comparedBook.Author.LastName, 
        StringComparison.OrdinalIgnoreCase);
}

1 test passed.

The code you are looking at is actually the result of the following tests:

Each step in building the CompareTo method was based on a failing test. Is this practical? Are these TDD tests which are not Unit tests? It's easy to write this many tests when you are writing at home in your PJ's, but what about real life? As a developer I write as many TDD tests as possible, but never enough Unit Tests. As long as I keep my code simple, TDD tests often cover the Unit Tests.

Please contact me about this Kata. I would love to get your feedback.

Now that we know how to compare books let's try some other sorting algorithms: