6

I spend some time implementing a quicksort algorithm in C#. After finishing I compared the speed of my implementation and C#'s Array.Sort-Method.

I just compare speed working on random int arrays.

Here's my implementation:

static void QuickSort(int[] data, int left, int right)
{
    int i = left - 1,
        j = right;

    while (true)
    {
        int d = data[left];
        do i++; while (data[i] < d);
        do j--; while (data[j] > d);

        if (i < j) 
        {
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }
        else
        {
            if (left < j)    QuickSort(data, left, j);
            if (++j < right) QuickSort(data, j, right);
            return;
        }
    }
}

Performance (when sorting an random int[] with length of 100000000):
   - my algorithm: 14.21 seconds
   - .Net Array<int>.Sort: 14.84 seconds

Does anyone know how to implement my algorithm even faster?
Or can anyone provide a faster implementation (need not be a quicksort!) which my run faster?

Note:
   - please no algorithms which use multiple cores/processors to improve perrformance
   - only valid C# source code

I will test the performance of the provided algorithms within a few minutes if I'm online.

EDIT:
Do you think using a ideal sorting network for parts containing less than 8 value would improve performance?

Improve this question
12
  • 4
    try repeating your timings when an array that is already sorted... Then with an array that only has two of the items in the wrong order.. Commented Sep 15, 2010 at 16:30
  • 2
    A performance gain of 4.3% - Are you doing this for academic reasons? Commented Sep 15, 2010 at 16:30
  • 2
    Ian is correct about the already sorted array. Your choice of a pivot element is going to have horrible worst-case performance. Having said that, speeding up Quicksort is fairly straightforward. Select a better pivot using something like the MedianOfThree method and use a more appropriate sorting algorithm for small partitions. I assume you are doing this for personal research because using the system-library sort method is almost always the right answer. Commented Sep 15, 2010 at 16:42
  • And you could unroll one of the recursive branches. I'm not sure if C#/JIT will do that. Commented Sep 15, 2010 at 16:49
  • 3
    I just finished: when trying to sort an already sorted array my algorithm gets terribly slow. Commented Sep 15, 2010 at 17:06

6 Answers 6

Reset to default
8

Binary insertion sort almost always wins for short runs (~10 items). It's often better than an ideal sorting network because of the simplified branching structure.

Dual pivot quicksort is faster than quicksort.

If you're only sorting integers, a radix sort will likely be faster still on long arrays.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

7

Does anyone know how to implement my algorithm even faster?

I was able to shave 10% off the execution time by converting your code to use pointers.

    public unsafe static void UnsafeQuickSort(int[] data)
    {
        fixed (int* pdata = data)
        {
            UnsafeQuickSortRecursive(pdata, 0, data.Length - 1);
        }
    }

    private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right)
    {
        int i = left - 1;
        int j = right;

        while (true)
        {
            int d = data[left];
            do i++; while (data[i] < d);
            do j--; while (data[j] > d);

            if (i < j)
            {
                int tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
            else
            {
                if (left < j) UnsafeQuickSortRecursive(data, left, j);
                if (++j < right) UnsafeQuickSortRecursive(data, j, right);
                return;
            }
        }
    }
Improve this answer

8 Comments

there is a little bug, but really nice upgrade (+1), 1.1 seconds faster on my hardware!
Doesn't this clash with the "safe" requirement in the title?
It's a bit difficult to say... this is simple enough too... I just wanted to be sure that I don't get any high optimized C/C++ codes.
@Gabe: I thought about that too before I posted. I was not really sure if "safe" was synonomous with "stable". But, considering that the quick sort is not stable that is probably a moot point anyway. I decided to go ahead and post anyway.
I would probably have the top level function either not have the left/right args or do some bounds checking before the call.
|
1

A faster sorting algorithm for arrays of random integers is LSD Radix Sort:

    public static int[] SortRadix(this int[] inputArray)
    {
        const int bitsPerDigit = 8;
        const uint numberOfBins = 1 << bitsPerDigit;
        uint numberOfDigits = (sizeof(uint) * 8 + bitsPerDigit - 1) / bitsPerDigit;
        int d;
        var outputArray = new int[inputArray.Length];

        int[][] startOfBin = new int[numberOfDigits][];
        for (int i = 0; i < numberOfDigits; i++)
            startOfBin[i] = new int[numberOfBins];
        bool outputArrayHasResult = false;

        const uint bitMask = numberOfBins - 1;
        const uint halfOfPowerOfTwoRadix = PowerOfTwoRadix / 2;
        int shiftRightAmount = 0;

        uint[][] count = HistogramByteComponents(inputArray, 0, inputArray.Length - 1);

        for (d = 0; d < numberOfDigits; d++)
        {
            startOfBin[d][0] = 0;
            for (uint i = 1; i < numberOfBins; i++)
                startOfBin[d][i] = startOfBin[d][i - 1] + (int)count[d][i - 1];
        }

        d = 0;
        while (d < numberOfDigits)
        {
            int[] startOfBinLoc = startOfBin[d];

            if (d != 3)
                for (uint current = 0; current < inputArray.Length; current++)
                    outputArray[startOfBinLoc[((uint)inputArray[current] >> shiftRightAmount) & bitMask]++] = inputArray[current];
            else
                for (uint current = 0; current < inputArray.Length; current++)
                    outputArray[startOfBinLoc[((uint)inputArray[current] >> shiftRightAmount) ^ halfOfPowerOfTwoRadix]++] = inputArray[current];

            shiftRightAmount += bitsPerDigit;
            outputArrayHasResult = !outputArrayHasResult;
            d++;

            int[] tmp = inputArray;       // swap input and output arrays
            inputArray = outputArray;
            outputArray = tmp;
        }
        return outputArrayHasResult ? outputArray : inputArray;
    }
    [StructLayout(LayoutKind.Explicit)]
    internal struct Int32ByteUnion
    {
        [FieldOffset(0)]
        public byte byte0;
        [FieldOffset(1)]
        public byte byte1;
        [FieldOffset(2)]
        public byte byte2;
        [FieldOffset(3)]
        public byte byte3;

        [FieldOffset(0)]
        public Int32 integer;
    }
    public static uint[][] HistogramByteComponents(int[] inArray, Int32 l, Int32 r)
    {
        const int numberOfBins = 256;
        const int numberOfDigits = sizeof(ulong);
        uint[][] count = new uint[numberOfDigits][];
        for (int i = 0; i < numberOfDigits; i++)
            count[i] = new uint[numberOfBins];

        var union = new Int32ByteUnion();
        for (int current = l; current <= r; current++)    // Scan the array and count the number of times each digit value appears - i.e. size of each bin
        {
            union.integer = inArray[current];
            count[0][union.byte0]++;
            count[1][union.byte1]++;
            count[2][union.byte2]++;
            count[3][((uint)inArray[current] >> 24) ^ 128]++;
        }
        return count;
    }

It runs at nearly 100 MegaInt32s/sec on a single core - about 7X faster than Array.Sort(), 25X faster than Linq.OrderBy() on a single core and 6X faster than Linq.AsParallel().OrderBy() on 6 cores.

This implementation is taken from the HPCsharp nuget package on nuget.org, which also has versions for sorting arrays of uint[], long[], and ulong[], as well as MSD Radix Sort, which adds float[] and double[] arrays and is in-place.

Improve this answer

1 Comment

Another algorithm that has recently been added to the HPCsharp nuget package (open source and free) is a Parallel Hybrid Merge Sort with Array.Sort() as the leaf-node of recursion. This algorithm runs over 40X faster than Array.Sort() on a 32-core AMD processor, and is still a generic sort algorithm
1

This is faster and simpler for me.

unsafe static void Sort(int* a, int length)
{
    int negLength = length - 1;
    for (int i = 0; i < negLength; ++i)
    for (int n = i + 1; n < length; ++n)
    {
        int value = a[i];
        int next = a[n];
        if (value > next)
        {
            a[i] = next;
            a[n] = value;
        }
    }
}
Improve this answer

Comments

0

Take a look at Shear Sort and Odd-Event Transposition sort: http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html and http://home.westman.wave.ca/~rhenry/sort/.

There's a C# implementation of Shear Sort here: http://www.codeproject.com/KB/recipes/cssorters.aspx.

The examples are in Java but that's awfully close to C#. They're parallel sorts because they run faster on multiple cores but still should be very fast.

Improve this answer

Comments

0

This first(and probably the second one) quick sort algorithm breaks when sorting arrays with duplicate items. I used this one, which works fine.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.