Quicksort

While the Quicksort is relatively fast, O(nlog(n)) in terms of speed on average, a lot of programmers fear it because they don’t like, understand, or maybe even know about recursion. 

Recursion is the process of a function calling itself. There is usually a slight penalty for recursion as each function call is slower than if it had been done in a loop. However, most recursion algorithms can be rewritten into a loop. However, this would be most difficult to do in that fashion.

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays. From Wikipedia

If we want to think about it in a general steps, we would:

1. First, select an element, called the pivot element. 
2. Next, compare all array elements with the selected pivot element and arrange them in such a way that, elements less than the pivot element are to it’s left and greater than pivot is to it’s right.
3. Finally, perform the same operations on left and right side elements to the pivot element. – This is the recursion process because we keep breaking down items to the left and right until they are just a single element and they cannot be further sorted.

Picking your pivot element is extremely important. If you pick your first (or last) element, you have made your sort very ineffective. You should pick the middle element in an array. So if you have an array of 11 elements, you would pick index 5 – so you would have five elements to the left, and five elements to the right. You might notice that this works best with an array, as trying to find the middle of a linked list could be cumbersome, especially if you don’t have an idea as to its size already.

Ideally, your middle element is also the middle value, but that is rare at best, and we can work without it.

The quick sort is a fast sorting algorithm and it doesn’t require the addition of additional lists/arrays like the merge sort does. This means it is less resource intensive and thus used in many places.

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot



def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

The same basic code in C# would look like:

static public int Partition(int[] numbers, int left, int right)
        {
            int pivot = numbers[left];
            while (true)
            {
                while (numbers[left] < pivot) 
                {
                    left++;
                }

                while (numbers[right] > pivot) 
                {
                    right--;
                }
 
                if(numbers[left] == numbers[right])
                {
                    return right;
                }
                
                if (left < right)
                {
                    int temp = numbers[right];
                    numbers[right] = numbers[left];
                    numbers[left] = temp;
                }
                else
                {
                    return right;
                }

            }

        }

 

        static public void SortQuick(int[] arr, int left, int right)
        {
            // For Recursion  
            if (left < right)
            {
                int pivot = Partition(arr, left, right);

                if (pivot > 1)
                    SortQuick(arr, left, pivot - 1);
 
                if (pivot + 1 < right)
                    SortQuick(arr, pivot + 1, right);
            }
        }

Note that in the C# version, you have use a temp variable to swap two values which you don’t have to in Python due to the language. Also, the Python example uses a sub function since it doesn’t require you to know the left and right (start and end) values of the array segment you are sorting. These are minor changes.

Quicksort was originally found on Access 2 Learn