Quicksort implementation in C#

Question

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];
        //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

    public void Sort()
    {
        // Calls the 'private' recursive Quicksort method
        recSort(0, data.Length-1);
    }

    private void recSort(int left, int right)
    {
        // Recursively calls itself until the pointers collide
        // And as the partitioning works in-place there's no
        // writing at the end, the array is already sorted
        if(left<right) {
            int pivot = Partition(left, right); 
            recSort(left, pivot-1);
            recSort(pivot+1, right);
        }

    }

    private int Partition(int left, int right)
    {
        // Takes the leftmost value of our input array
        // and puts it in its correct final position
        // ie. all values larger than it above and all values
        // lower than it below

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

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

            if(i<j)
                Swap(i,j);

            do {
                i++;
            } while (data[j]>data[i]);

            if(i<j)
                Swap(i,j);
        }

        return j;
    }

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

    public override string ToString()
    {
        // Display a pretty version of the array
            // Make sure SB doesn't have to increase capacity as it appends
        StringBuilder temp = new StringBuilder((data.Length*6)+1);

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

        return temp.ToString();
    }

} // end class

Sample output (with debugging turned on) looks like this:

Exercise 24.10 - Quicksort


Unsorted: [64] [48] [79] [43] [75] [54] [81] [94] [75] [66] [57] [61]

SW 64/61: [61] [48] [79] [43] [75] [54] [81] [94] [75] [66] [57] [64]
SW 79/64: [61] [48] [64] [43] [75] [54] [81] [94] [75] [66] [57] [79]
SW 64/57: [61] [48] [57] [43] [75] [54] [81] [94] [75] [66] [64] [79]
SW 75/64: [61] [48] [57] [43] [64] [54] [81] [94] [75] [66] [75] [79]
SW 64/54: [61] [48] [57] [43] [54] [64] [81] [94] [75] [66] [75] [79]
SW 61/54: [54] [48] [57] [43] [61] [64] [81] [94] [75] [66] [75] [79]
SW 54/43: [43] [48] [57] [54] [61] [64] [81] [94] [75] [66] [75] [79]
SW 57/54: [43] [48] [54] [57] [61] [64] [81] [94] [75] [66] [75] [79]
SW 81/79: [43] [48] [54] [57] [61] [64] [79] [94] [75] [66] [75] [81]
SW 94/81: [43] [48] [54] [57] [61] [64] [79] [81] [75] [66] [75] [94]
SW 81/75: [43] [48] [54] [57] [61] [64] [79] [75] [75] [66] [81] [94]
SW 79/66: [43] [48] [54] [57] [61] [64] [66] [75] [75] [79] [81] [94]
SW 75/75: [43] [48] [54] [57] [61] [64] [66] [75] [75] [79] [81] [94]

  Sorted: [43] [48] [54] [57] [61] [64] [66] [75] [75] [79] [81] [94]

I really am hoping for some guidance on how I could have done things better, perhaps things I've done well, and general stuff like how I've designed my class/methods, general style etc.

Answer 1

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.

Answer 2

Today in c# 7 you can write all quicksort in "one line"

static IEnumerable<int> QuickSort(IEnumerable<int> list) =>
    list.FirstOrDefault() is var head  &&
    list.Skip(1) is var tail &&
    tail.Where(e => e >= head) is var larger &&
    tail.Where(e => e < head) is var smaller &&
     !list.Any()
      ? Enumerable.Empty<int>()
      : QuickSort(smaller).Append(head).Concat(QuickSort(larger));

UPDATE:

C# 12 "one line"

int[] QuickSort(int[] numbers) => 
    numbers switch {
        [] => [],
        [var head, ..var tail] => [
            ..QuickSort(Array.FindAll(tail, n => n <= head)),
            head,
            ..QuickSort(Array.FindAll(tail, n => n > head))
        ]
    };

Answer 3

One thing that comes to mind is that you don't need to retain an instance of Random in your QuickSort class. Since it is only used during initialization, the Random instance should be a variable in the constructor, which would allow it to be garbage-collected as soon as the constructor is done.