Is This a QuickSort?

Question

I'm trying to write a quicksort for my own edification. I'm using the pseudocode on wikipedia as a guide. My code works. It seems like it should run in O(n log n) time. I tried actually timing my code to check the complexity (i.e., when I double the input size, does the run time increase by approximately n log n), but I'm still not sure.

My code seems pretty simple. I do the sort in-place. Other implementations I've seen use a partition function, which I don't have. This makes me think that I've implemented some other sorting algorithm. Is this a quicksort algorithm?

public static void QuickSortInPlace(int[] arr)
{
    QuickSortInPlace(arr, 0, arr.Length - 1);
}

private static void QuickSortInPlace(int[] arr, int left, int right)
{
    if (left < right)
    {
        //move the middle int to the beginning and use it as the pivot
        Swap(arr, left, (left + right) / 2);

        int pivotIndex = left;
        int pivot = arr[pivotIndex];
        int min = left + 1;
        int max = right;

        for (int i = min; i <= max; i++)
        {
            if (arr[i] > pivot)
            {
                Swap(arr, i, max);
                max--; //no longer need to inspect ints that have been swapped to the end
                i--; //reset the loop counter to inspect the new int at the swapped position
            }
        }

        //move pivot to its sorted position
        Swap(arr, max, pivotIndex);

        //recurse on the sub-arrays to the left and right of the pivot
        QuickSortInPlace(arr, left, max - 1);
        QuickSortInPlace(arr, max + 1, right);
    }
}

Second version based on Dukeling's response.

public static void QuickSortInPlace3(int[] arr, int min, int max)
{
    if (min < max)
    {
        int pivotIndex = min;
        int pivot = arr[pivotIndex];

        int left = min;
        int right = max;

        while (left <= right)
        {
            while (arr[left] < pivot)
                left++;

            while (arr[right] > pivot)
                right--;

            if (left <= right)
            {
                Swap(arr, left, right);
                left++;
                right--;
            }
        }

        QuickSortInPlace3(arr, min, right);
        QuickSortInPlace3(arr, left, max);
    }
}

Answer 1

Yes, it's definitely close enough to quicksort to classify as that, or at least a minor variant.

You are partitioning the data, you just don't have a separate function for it.

You do have something a bit strange happening.

Normally, with the in-place variant of quicksort, you increase the left index while it's smaller than the pivot, then you decrease the right index while it's larger, then you swap the two (as to only perform swaps involving 2 elements which are both on the wrong side).

You are, however, just increasing the left, so you could swap already larger elements from the right. This could result in a few more swaps than necessary, although the asymptotic running time should be the same.

Here's some pseudo-code of the 'normal' variant: (taken from Rosetta Code)

while left ≤ right
    while array[left] < pivot
        left := left + 1
    while array[right] > pivot
        right := right - 1
    if left ≤ right
        swap array[left] with array[right]
        left := left + 1
        right := right - 1