4
\$\begingroup\$

I'm currently learning programming for the first time and I've created the following implementation of quick sort in C#. I basically read a very basic overview of how quick sort works recursively and implemented it without looking at any concrete examples of its implementation so that I could learn the most from it.

Could you let me know what you think and where it could be optimized?

class Program
{
    static void Main(string[] args)
    {
        var input = new int[] {  10, 3, 20, 5, 200 };
        QuickSort(0, 0, input.Length-1, input);
        Console.WriteLine("Sorted output: :");
        new List<int>(input).ForEach(x => Console.Write(x + ","));
        Console.ReadLine();
    }

    /// <summary>
    /// sample input: 5 7 3 9 2
    /// same output: 2 3 5 7 9
    /// </summary>
    /// <param name="numbers"></param>
    public static void QuickSort(int pivotIndex, int startIndex, int endIndex, int[] numbers)
    {
        if (startIndex == endIndex) return;

        int pivotNumber = numbers[pivotIndex];

        var lowerThanPivot = new List<int>();
        var higherThanPivot = new List<int>();

        for(int i = startIndex; i <= endIndex; i++)
        {
            if(i != pivotIndex)
            {
                if( numbers[i] <= pivotNumber )
                    lowerThanPivot.Add(numbers[i]);
                else
                    higherThanPivot.Add(numbers[i]);
            }
        }

        // now lets put the pivot number in the correct place
        numbers[startIndex + lowerThanPivot.Count] = pivotNumber;

        // reinsert the numbers lower than pivot in the right place
        int z = startIndex;
        lowerThanPivot.ForEach(x => numbers[z++] = x);

        z++; // *** skip over the new pivot index ***

        // reinsert the numbers higher than pivot in the right place
        higherThanPivot.ForEach(x => numbers[z++] = x);

        // recursively call to sort each remaining elements

        int newLeftPivot = startIndex;
        int newEndLeftIndex = newLeftPivot + lowerThanPivot.Count - 1 ;

        int newRightPivot = lowerThanPivot.Count + 1;
        int newEndRightIndex = newRightPivot + higherThanPivot.Count - 1;


        if(lowerThanPivot.Count> 0)
            QuickSort(newLeftPivot, newLeftPivot, newEndLeftIndex, numbers);

        if(higherThanPivot.Count > 0)
            QuickSort(newRightPivot, newRightPivot, newEndRightIndex, numbers);

    }
}
\$\endgroup\$
6
\$\begingroup\$
new List<int>(input).ForEach(x => Console.Write(x + ","));

I see absolutely no reason to do this. In general, List.ForEach() is considered bad form by some and you should use normal foreach instead.

/// <summary>
/// sample input: 5 7 3 9 2
/// same output: 2 3 5 7 9
/// </summary>
/// <param name="numbers"></param>

This is not a very good documentation comment. The comment should describe in words what your code does. Example input and output might help to clarify that further, but I think that's not necessary for sorting.

Also, you should either describe your parameters using <param>, or don't use it (if you think the meaning of the parameters is clear). But empty <param> is not useful.

var lowerThanPivot = new List<int>();
var higherThanPivot = new List<int>();

You don't need these two lists. QuickSort can be implemented as an in-place algorithm. That means you don't need any additional collections to use it.

The way this is done is that you iterate the array from the start and at the same time from the end, switching elements between the two positions if the left one is larger than the pivot and the right one is smaller.

This will make your code somewhat more complicated, but it also potentially saves a lot memory.

int newLeftPivot = startIndex;

int newRightPivot = lowerThanPivot.Count + 1;

This is not a very good choice for a pivot. If the array is already sorted (or mostly sorted, with often isn't that uncommon), then your code will run in O(n^2) time, which will make it very slow on large inputs. You should consider a better way to choose the pivot.

\$\endgroup\$

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.