Quicksort implementation in C#

Okay, so I'm a self-taught programmer and have been brushing up on all the 'boring' bits that CS students do that most of us self-taught ignore. Things like Algorithms and Data Structures (particularly). So I found a nice exercise book that explains how algorithms work, but then leaves the implementation to the reader.

This works well for me as I'm the kind of person for whom knowledge 'sticks' better if I can "figure it out for myself".

So, I've just finished the Chapter on Sorting and quite easily managed to implement working Bubble Sort, Radix Sort, Mergesort etc. I really struggled getting Quicksort to work though - lots of out of bounds errors that I found hard to track down. So, now I do have it working - I'm wondering whether I just set about coding the algorithm (I'm using C#) the wrong way in the first place.

So, my question, I'll post my code below, and I'd really appreciate it if you guys could tell me (mentor style I guess) how I could have done a better job if I did it again. What I don't want is a long discussion of "you chose a silly pivot value", remember I implemented this from an exercise and that told me explicitly to use the left-most value of each sub-array as the pivot for each partition.

So, here's the code that basically creates the object and calls the sort method:

class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Exercise 24.10 - Quicksort\n\n");

            Quicksort sort = new Quicksort(12);

            Console.WriteLine("Unsorted: {0}\n", sort);

            sort.Sort();

            Console.WriteLine("\n  Sorted: " + sort);

            Console.Write("\nPress any key to continue . . . ");
            Console.ReadKey(true);
        }
    }

and here's the object that implements the Quicksort & the partitioning:

```
class Quicksort
{
private int[] data;
private Random rng = new Random();

public Quicksort(int size)
{
data = new int[size];

I really like how you're keeping the Program class nice and clean, and that the first thing you do is instantiate a class that encapsulates the logic you want to run.

However you have mixed concerns there, it shouldn't be QuickSort's job to generate the data to be sorted, and this:

Quicksort sort = new Quicksort(12);

Is rather off-putting when you realize that the 12 is really...

public Quicksort(int size)
{
    data = new int[size];
    //Test Data from TextBook:
    //data = new int[] {37, 2, 6, 4, 89, 8, 10, 12, 68, 45};

    // Generate some Random Data
    for(int i=0; i<data.Length;i++)
        data[i]=rng.Next(0,100);

} // end constructor

...the size of the array we want to generate random numbers for... @Zoyd's answer is correct, the Random instance is pretty.. random there. In fact, it doesn't belong in QuickSort at all.

While I'm here, this:

} // end constructor

Is not a comment, it's noise. Remove it, and anything similar (like, // end class).

Let's look at your public interface:

public Quicksort(int size)
public void Sort()
public override string ToString()

I realize this isn't touching your implementation and only scratches the surface, but just by looking at these three lines it's possible to see what's sloppy. I'd be expecting something like this:

public Quicksort()
public void Sort(int[] data)

Because Sort has a side-effect - it sorts the int[] data parameter. The QuickSort class itself doesn't shouldn't own the data, so overriding ToString to output that data makes no sense, at least not if you're trying to be following the Single Responsibility Principle.

Let's see what's under the hood:

private void recSort(int left, int right)
private int Partition(int left, int right)
private void Swap(int i, int j)

The only thing I don't like, is the name of recSort - its casing isn't consistent (should be PascalCase), and is it RecordSort, RecreationalSort, or RecursiveSort? Keep names meaningful, don't chop them off just because you know what it stands for.

This is a little hard to read:

while(i<j) {
        do {
            j--;
        } while (data[i]<data[j]);

Why? Because the bracing style isn't consistent here either: those are Java-style opening braces, C# conventions put the opening brace { on the next line. Also don't try to compact everything, let it breathe!

while (i < j) 
    {
        do 
        {
            j--;
        } 
        while (data[i] < data[j]);

        //...

This is also a naming opportunity:

int i=left; // i is our bot->top travelling "pointer"
int j=right+1;  // j if our top->bot travelling "pointer"

The comments could be removed if the "pointers" had more descriptive names:

int bottomUpIndex = left;
int topDownIndex = right + 1;

This is interesting:

// DEBUG: Uncomment to show swap details
    //Console.WriteLine  ("SW {0:00}/{1:00}: {2}",data[j],                   
        //data[i],this.ToString());

This is going to be WAY overkill for your little exercise, but if you went with a SOLID architecture, you could have an ISwapable interface injected as a dependency to your QuickSort implementation (in the class' constructor):

public interface ISwapable
{
    void Swap(int[] data, int indexA, int indexB);
}

And then you could have a basic implementation that does the swapping, and a decorator that does the debug output - and you decide which ISwapable implementation you want to inject at start-up:

public class DebugOutputSwapDecorator : ISwapable
{
    private readonly ISwapable _swapper;

    public DebugOutputSwapDecorator(ISwapable swapper)
    {
        _swapper = swapper;
    }

    public void Swap(int[] data, int indexA, int indexB)
    {
        _swapper.Swap(data, indexA, indexB);
        DisplaySwappingResult(data, data[indexA], data[indexB]);
    }

    private void DisplaySwappingResult(int[] data, int valueA, int valueB)
    {
        StringBuilder builder = new StringBuilder((data.Length * 6) + 1);

        for (int i = 0; i < data.Length; i++)
            builder.AppendFormat("[{0:00}] ", data[i]);

        Console.WriteLine("SW {0}/{1}: {2}", valueA, valueB, builder.ToString());
    }
}

...and by SOLID's principles the QuickSort class would have no clue that its ISwapable dependency is really outputting the values to the console (it's none of its concern), and instead of having to find the lines of code to comment/uncomment to toggle between behaviors, you could just change the ISwapable implementation you're passing to QuickSort's constructor when you're creating it in your Main method.

Obviously there'd be a little more work needed to keep everything DRY (DisplaySwappingResult does more than it needs to be doing here), but you get the idea.

As for the sorting itself, I like how you've split it into small methods. Nothing to add, really.

StackExchange Code Review Q#48773, answer score: 6