Question about Quick Sort : Partition Method

[sciprog22]

Hello,

Thank you for your time!

I am trying to understand the Quick Sort algorithm. I have some questions about the partition method. I found the following implementation online:

import java.util.Scanner;

public class QuickSorts
{

    public static int partition(int a[], int left, int right, int size)
    {
        int pivot = a[left];
        boolean flag =true;

        while (flag)
        {
            if (a[left] < pivot)
            {
                left++;
            }
            if (a[right] > pivot)
            {
                right--;
            }
            if (left < right)
            {
                int temp = a[left];
                a[left] =  a[right];
                a[right] = temp;
            }
            else
            {
                flag = false;

            }
        }

        return right;
    }

    public static void quicksort(int a[], int left, int right, int size)
    {
        if (left < right)
        {
            int pivot = partition(a, left, right, size);
            quicksort(a, left, pivot-1, size);
            quicksort(a, pivot+1, right, size);
        }
    }

    public static void main(String args[])
    {
        int a[] = {12,1,0,9,56,7,2,8};
        int size = a.length;
        System.out.print ("Starting Array:");
        for (int i =0; i<size; i++)
        {
            System.out.print(a[i] + " ");

        }
        System.out.println();
        quicksort(a, 0, size -1, size);
        for (int i =0; i<size; i++)
        {
            System.out.print(a[i] + " ");
        }
    }
}

So far, I understand the following:

1) The quicksort is a process of placing the pivot(left most value in this program) in the appropriate cell# of the input array such that values to its left < pivot and values to the right > pivot

2) The quick sort method calls the partition method (as described above) recursively on both sub-arrays of the pivot.

Step#2 makes sense. The objective of the partition method in Step#1 makes sense as well, but not the logic of how it works. When I printed the input array inside the while loop of the partition method, I get the following:

Starting Array:12 1 0 9 56 7 2 8

8 1 0 9 56 7 2 12
8 12 0 9 56 7 2 1
8 1 0 9 56 7 2 12
8 1 12 9 56 7 2 0
8 1 0 9 56 7 2 12
8 1 0 12 56 7 2 9
8 1 0 9 56 7 2 12
8 1 0 9 12 7 2 56
8 1 0 9 2 7 12 56
8 1 0 9 2 12 7 56
8 1 0 9 2 7 12 56
8 1 0 9 2 7 12 56

This clearly works and is very elegant in its implementation.There is no way I could have written this method from scratch!

I would have used two arrays, one to store values < pivot and the other values > pivot and copied it back to the original array into the proper cells. But the space complexity of my method would be O(n), which is clearly inferior to the O(1) of the above implementation.

If possible, could you explain me the idea behind writing the partition as mentioned above?

Thank you!

[gusano79]

8 1 0 9 2 7 12 56
This clearly works and is very elegant in its implementation.

Is that the last result? Because it's clearly not sorted...

Ah, I see. It's the first partition, not the end state. Sorry, disregard.

If possible, could you explain me the idea behind writing the partition as mentioned above?

In other words, do you mean "how does partition work?"

[rubberman]

Basically, it is a binary sort that on average requires O(n log n) comparisons to sort, though it is often more efficient that that. Here is the Wikipedia article that does a decent job of explaining the details: https://en.wikipedia.org/wiki/Quicksort

If you are inserting items into a sorted array, then you can use a version of this as in insertion sort. When you do that though, you want to do head and tail optimizations (look to see if the new entry should go to the head or tail of the array). Doing that adds two comparisons to the overhead, but adding items to a sorted array can create a huge speedup. An example of that situation is to insert output from an SQL select statement with an orderby clause, causing the output to be sorted before inserting in the array.

I have personally implemented these algorithms in major commercial application frameworks.

[sciprog22]

Hello rubberman - Thank you for the reply!

Thanks to gusano79 as well

Regards