3
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Surprised to see DI even suggested for such a low level operation. \$\endgroup\$ – Frank Hileman May 2 '14 at 16:48
  • \$\begingroup\$ @Frank I know, ...I thought the same thing too. I guess the commenting/uncommenting of debug output tripped something in my abstraction-freak's brain ;) \$\endgroup\$ – Mathieu Guindon May 2 '14 at 16:51
  • 2
    \$\begingroup\$ @Frank and Mat, actually I found it quite an interesting idea. Starting off, as I did, in standard ANSI C I would have done this 'the good old days' using #if debug pre-processor directives. So, I was completely unaware of this (quite elegant) way of doing things in a 'proper' OOP language. Once again, thanks guys! \$\endgroup\$ – Th3Minstr3l May 6 '14 at 13:24
4
\$\begingroup\$

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));
\$\endgroup\$
  • 2
    \$\begingroup\$ This is really nice but I consider this as a Code Golf solution that has no place in production code ;-) Btw, you can replace one of the Concats with Append and it would be great if you could explain your solution a bit because well, this is Code Review and not Code Golf... \$\endgroup\$ – t3chb0t Apr 15 '18 at 6:44
  • \$\begingroup\$ @t3chb0t this isn't code-golf; far too clear, and look at all those gratuitous variable declarations! I do agree some explanation (and perhaps justification!) is in order, however! \$\endgroup\$ – VisualMelon Apr 15 '18 at 15:05
  • \$\begingroup\$ @VisualMelon it isn't clear at all ;-) no sane person would ever build such an expression concatenated with ANDs using tricky inline variables. Code-golf it is :-P it's not even functional but it's fun ;-) \$\endgroup\$ – t3chb0t Apr 15 '18 at 15:11
  • \$\begingroup\$ @t3chb0t well, we'll have to differ on our definitions; if this was codegolf.SE, the answer might get a down-vote from me for lack of effort ;) a big problem with this asnwer is that it won't work if the pivot appears more than once, and doesn't have the partitioning implemented in the OP, so can't possibility qualify as an answer, let alone a review in it's current form. \$\endgroup\$ – VisualMelon Apr 15 '18 at 15:28
  • 1
    \$\begingroup\$ @LucasTeles I'd not actually noticed that... the problem whereto I refer is that any elements in tail which are equal to the pivot will be lost, you need something like tail.Where(e => e >= head) is var larger &&. \$\endgroup\$ – VisualMelon Jun 11 '18 at 12:31
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ah, yes - you're absolutely right! I guess I was thinking that a Sort object wouldn't - in reality - 'create' any data (normally it'd take an unsorted array as input) so my whole constructor/use of random is 'fake'. So I was sloppy in how I implemented that for sure. Thank you. \$\endgroup\$ – Th3Minstr3l May 2 '14 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.