Sorting Kata - Quick 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 Quick 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.QuickSort(books, 0, books.Count - 1);

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

We use CTRL+. to add the QuickSort 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> QuickSort( List<Book> books, 
                                           int leftIndex, 
                                           int rightIndex )
        {
            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> QuickSort( List<Book> books, 
                                           int leftIndex, 
                                           int rightIndex )
        {
            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 Quick Sort algorithm defined on Sorting-Algorithms.com is:

Quick Sort
void quicksort(Item a[], int l, int r)
{ 
    int i = l-1, j = r; Item v = a[r];
    
    if (r <= l) return;

    for (;;)
    {
        while (a[++i] < v) ;
        while (v < a[--j]) if (j == l) break;
        if (i >= j) break;
        exch(a[i], a[j]);
    }

    exch(a[i], a[r]);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
}

This is the hardest of the three Quick Sort algorithms from the Sorting-Algorithms.com Quick Sort page.

Working on Quick Sort felt a lot like Merge Sort. The difference was instead of recursion at the beginning, we do it at the end.

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

BookSorting/Bookshelf.cs
public List<Book> QuickSort(List<Book> books,
                                    int leftIndex,
                                    int rightIndex)
{
    var firstIndex = leftIndex;
    var lastIndex = rightIndex - 1;
    var leftsideIndex = leftIndex;
    var rightsideIndex = rightIndex;

    if (rightIndex <= leftIndex)
    {
        return books;
    }

    var currentBook = books[rightIndex];

    Book swap;

    for (int i = 0; i < books.Count; i++)
    {
        while (books[firstIndex] > currentBook)
        {
            firstIndex++;
        }

        while (currentBook > books[lastIndex])
        {
            lastIndex--;
            if (lastIndex == leftIndex)
            {
                break;
            }
        }

        if (firstIndex >= lastIndex)
        {
            break;
        }

        swap = books[firstIndex];
        books[firstIndex] = books[lastIndex];
        books[lastIndex] = swap;

        if (books[firstIndex] == currentBook)
        {
            leftsideIndex++;
            swap = books[leftsideIndex];
            books[leftsideIndex] = books[firstIndex];
            books[firstIndex] = swap;
        }

        if (currentBook == books[lastIndex])
        {
            rightsideIndex--;
            swap = books[lastIndex];
            books[lastIndex] = books[rightsideIndex];
            books[rightsideIndex] = swap;
        }
    }

    swap = books[firstIndex];
    books[firstIndex] = books[rightIndex];
    books[rightIndex] = swap;

    lastIndex = firstIndex - 1;
    firstIndex++;

    for (int k = leftIndex; k < leftsideIndex; k++)
    {
        lastIndex--;
        swap = books[k];
        books[k] = books[lastIndex];
        books[lastIndex] = swap;
    }

    for (int k = rightIndex - 1; k > rightsideIndex; k--)
    {
        firstIndex++;
        swap = books[firstIndex];
        books[firstIndex] = books[k];
        books[k] = swap;
    }

    QuickSort(books, leftIndex, lastIndex);
    QuickSort(books, firstIndex, rightIndex);

    return books;
}

Method Signature

Calling this algorithm is different because it needs more information than the other ones. We need the list, where to start, and where to end. Each time we call the method, we use the same list. With the other algorithms we used a modified list. Because we are using the same list, we have to pass in indexes.

Variables

Indexes are used heavily in this algorithm. The leftIndex tells us where to start. The rightIndex tells where to stop. We copy these indexes into other variables that will be incremented during the loop.

Despite its complexity, this is how I would sort the bookshelf if there were a lot of books. The books are placed either ahead or after a chosen book.

Mobile Wire Book Cart

You would put all of the authors starting with A on the top of the cart. Then B's on the bottom. Once you are in the section where the books go, you would sort just the A authors. Then you would sort the B authors as you place them on the shelf. That's what the Quick Sort is doing. It puts all of the books either before or after a selected book. Then it recursively selects another book. The index make sure we are putting the books into the proper place in the list.

I think this one exceeds the bounds of a simple Kata. I should have chosen a smaller algorithm. We are saved in the fact that each loop does only one simple thing. It moves the index.

The outer loop moves us through each book. Inner loops adjust the index so that we know where the book should be placed in the list. Once the indexes are changed, we swap the books.

swap = books[firstIndex];
books[firstIndex] = books[rightIndex];
books[rightIndex] = swap;

After we swap the books we check to see if there are any other books to swap. Then we do it all over again for a smaller set.

In the end we have a sorted list.

When we run the test we see:

1 test passing

Conclusion

This is the last sorting algorithm I'm going to tackle for awhile. Going through this exercise has moved me up to level 1 of Sijin Joseph's Programmer Competency Matrix.

I like to reflect on what I have learned. I feel like the Kata could have stopped at Linq. This is how I would sort things. Each language has a way to sort things. You could just practice two or three of them and that would be enough.

However, learning Bubble and the other ways to sort did expand my knowledge of overloading operators.

I think this series was worth the effort.

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

Other sorting methods: