snippetcsharpModerate

QuickSort C# Implementation

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

implementationquicksortstackoverflow

Problem

It has been a while since I've implemented a QuickSort and I wanted to write it down like I remembered.

int MyPartition(List list, int left, int right)
{
    int pivot = list[left];

    while(true)
    {
        while(list[left]  pivot)
            right--;

        if(list[right] == pivot && list[left] == pivot)
            left++;

        if(left  list, int left, int right)
{
    if(list == null || list.Count  1)
            MyQuickSort(list, left, pivotIdx - 1);

        if(pivotIdx + 1 < right)
            MyQuickSort(list, pivotIdx + 1, right);
    }
}

Sample usage:

var list = RandomList(1000);
MyQuickSort(list, 0, list.Count - 1);

Solution

With QuickSort, the complexity always comes down to two things:

how you deal with equal numbers (duplicates)

which index you use to return from the partition (left or right)

You need to decide up-front whether the pivot value is going to be in the left partition, or the right partition. If the pivot is going to be in the left, then you need to return left index, and the left partition is values



It is common practice for the 'right' index to start at the length (i.e. to be 1 after the last member).



you have odd handling for the duplicate value case

you are returning right instead of left




you are not swapping the pivot to where it belongs.... The point of the partitioning is that you are supposed to end up with the pivot value where it belongs.



you are not checking for left >= right on the increment side of the partition loops



The odd handling of duplicates is because the 'left' loop should be a

<= loop, not a <

 loop:

while(list[left] <= pivot)
            left++;


and you should get rid of the condition:

if(list[right] == pivot && list[left] == pivot)
            left++;


You should return

left

.

Then, in the Recursive call, you have the constant value

 which you use to test the left-condition.... This is a big bug, because the pivot will only return 0 for the left-most partition. The

1 constant should be left` ....

I ended up ideoning your code to play with it. IU shuffled around a lot of the logic.

Have a look...

This is the code that does the sort closer to the way that I expect:

using System;
using System.Collections.Generic;

public class Test
{
    static List RandomList(int size) {
        List ret = new List(size);
        Random rand = new Random(1);
        for (int i = 0; i  list, int left, int right)
    {
        int start = left;
        int pivot = list[start];
        left++;
        right--;

        while(true)
        {
            while(left  pivot)
                right--;

            if(left > right)
            {
                list[start] = list[left - 1];
                list[left - 1] = pivot;

                return left;
            }

            int temp = list[left];
            list[left] = list[right];
            list[right] = temp;

        }
    }

    static void MyQuickSort(List list, int left, int right)
    {
        if(list == null || list.Count  list) {
        list.ForEach(delegate(int val)
        {
            Console.Write(val);
            Console.Write(", ");
        });
        Console.WriteLine();
    }

    public static void Main()
    {
        List list = RandomList(100);
        DumpList(list);
        MyQuickSort(list, 0, list.Count);
        DumpList(list);
    }
}

Code Snippets

while(list[left] <= pivot)
            left++;

if(list[right] == pivot && list[left] == pivot)
            left++;

using System;
using System.Collections.Generic;

public class Test
{
    static List<int> RandomList(int size) {
        List<int> ret = new List<int>(size);
        Random rand = new Random(1);
        for (int i = 0; i < size; i++) {
            ret.Add(rand.Next(size));
        }
        return ret;
    }

    static int MyPartition(List<int> list, int left, int right)
    {
        int start = left;
        int pivot = list[start];
        left++;
        right--;

        while(true)
        {
            while(left <= right && list[left] <= pivot)
                left++;

            while(left <= right && list[right] > pivot)
                right--;

            if(left > right)
            {
                list[start] = list[left - 1];
                list[left - 1] = pivot;

                return left;
            }


            int temp = list[left];
            list[left] = list[right];
            list[right] = temp;

        }
    }

    static void MyQuickSort(List<int> list, int left, int right)
    {
        if(list == null || list.Count <= 1)
            return;

        if(left < right)
        {
            int pivotIdx = MyPartition(list, left, right);
            //Console.WriteLine("MQS " + left + " " + right);
            //DumpList(list);
            MyQuickSort(list, left, pivotIdx - 1);
            MyQuickSort(list, pivotIdx, right);
        }
    }

    static void DumpList(List<int> list) {
        list.ForEach(delegate(int val)
        {
            Console.Write(val);
            Console.Write(", ");
        });
        Console.WriteLine();
    }

    public static void Main()
    {
        List<int> list = RandomList(100);
        DumpList(list);
        MyQuickSort(list, 0, list.Count);
        DumpList(list);
    }
}

Context

StackExchange Code Review Q#47128, answer score: 19

Revisions (0)

No revisions yet.