Sorting Kata - Selection 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.

In List Sort we used the built-in sort method of a list. This required us to implement IComparable in the Book class.

In Bubble Sort we overloaded the < and > operators so that books could be sorted through a simple sort.

Here is our Book class.

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)
        {
            // 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);
        }

        public static bool operator >(Book book, Book comparedBook)
        {
            return comparedBook.CompareTo(book) > 0;
        }

        public static bool operator <(Book book, Book comparedBook)
        {
            return comparedBook.CompareTo(book) < 0;
        }
    }
}

Now we are going to write our own Selection Sort method.

We write a failing test first.

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
                {
                    Author = new Author
                        {
                            LastName = "Partnoy",
                            FirstName = "Frank",
                        },
                    Title = "Wait: The Art and Science of Delay",
                };

            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. SelectionSort(books);

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

We use CTRL+. to add the SelectionSort 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> SelectionSort(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> SelectionSort(List<Book> books)
        {
            return books;
        }
    }
}

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.

The Selection Sort algorithm defined on Sorting-Algorithms.com is:

Selection Sort
for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    -> invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    -> invariant: a[1..i] in final position
end

Let's translate this into C#. Instead of a, i, k, and n, I'm going to give the variables longer names.

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

namespace BookSorting
{
    public class Bookshelf
    {
        public List<Book> SelectionSort(List<Book> books)
        {
            for (int bookIndex = 0; bookIndex < books.Count; bookIndex++)
            {
                var selectedBookIndex = bookIndex;
                for (int allBooksIndex = bookIndex + 1; allBooksIndex < books.Count; allBooksIndex++)
                {
                    if (books[allBooksIndex] > books[selectedBookIndex])
                    {
                        selectedBookIndex = allBooksIndex;
                    }
                }

                if (selectedBookIndex != bookIndex)
                {
                    var swapBook = books[bookIndex];
                    books[bookIndex] = books[selectedBookIndex];
                    books[selectedBookIndex] = swapBook;
                }
            }

            return books;
        }
    }
}

Let me explain why this code differs from the algorithm.

Outer Loop

The first book's index is zero. We will be comparing a book to all of the other books on the shelf. We keep looping through the books as long as bookIndex is less than the number of books. We add 1 to bookIndex to keep moving through the list.

We set a variable selectedBookIndex to bookIndex so that we can see if we found a book that precedes the currently selected book.

Inner Loop

Our inner loop starts with the book that is next to the one defined in the outer loop. If you are looking at the book shelf. You would grab the second book and compare it to the first book. If the book you are holding precedes the book that is next to it, update selectedBookIndex. I reversed the > symbol in my loop from the one defined in the algorithm because I want the books in ascending order.

After looking at each book, we swap books by taking the book off the shelf and putting it in a swapBook variable. Then we select the book that precedes it and put it in the book's spot. Then we put the book into that empty slot.

When we run the test we see:

1 test passing

Conclusion

I recommend setting a breakpoint and watching the list of books change order.

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