Algorithm to partition the array using the pivot element

Question

I was trying to solve following programming exercise from some java programming book

Write method that partitions the array using the first element, called a pivot. After the partition, the elements in the list are rearranged so that all the elements before the pivot are less than or equal to the pivot and the elements after the pivot are greater than the pivot. The method returns the index where the pivot is located in the new list. For example, suppose the list is {5, 2, 9, 3, 6, 8}. After the partition, the list becomes {3, 2, 5, 9, 6, 8}. Implement the method in a way that takes at most array.length comparisons.

I've implemented solution, but it takes much more than array.length comparisons.

The book itself has solution, but unfortunately it's just plain wrong (not working with some inputs). I've seen the answer to this similar question, and understood "conquer" part of Quicksort algorithm, but in this algorithm values are partitioned using mid-value, but in my case using of 1st array value as a pivot is required.

• samgak: What is your question?
• Anup: No I mean this is the general form of partition it will take only O(n) comparisons as u will compare the pivot with all the other elements.
• Adriaan Koster: You have to show us your best attempt in code and explain exactly what unexpected results you are getting.
• amit: This is the partition from quicksort. You can find a pseudo code for it in wikipedia's quick sort article

Answer 1

This is the pivot routine from the linked answer (adapted from source here).

 int split(int a[], int lo, int hi) {
 // pivot element x starting at lo; better strategies exist
 int x=a[lo]; 
 // partition
 int i=lo, j=hi;
 while (i<=j) {
 while (a[i]<x) i++;
 while (a[j]>x) j--;
 if (i<=j) swap(a[i++], a[j--]);
 }
 // return new position of pivot
 return i;
 }

The number of inter-element comparisons in this algorithm is either n or n+1; because in each main loop iteration, i and j move closer together by at exactly c units, where c is the number of comparisons performed in each of the inner while loops. Look at those inner loops - when they return true, i and j move closer by 1 unit. And if they return false, then, at the end of the main loop, i and j will move closer by 2 units because of the swap.

This split() is readable and short, but it also has a very bad worst-case (namely, the pivot ending at either end; follow the first link to see it worked out). This will happen if the array is already sorted either forwards or backwards, which is actually very frequent. That is why other pivot positions are better: if you choose x=a[lo+hi/2], worst-case will be less common. Even better is to do like Java, and spend some time looking for a good pivot to steer clear from the worst case. If you follow the Java link, you will see a much more sophisticated pivot routine that avoids doing extra work when there are many duplicate elements.

• Vladimir Nabokov: you have a problem : for example , array: {2,3,4,7,1,8,9}, pivot is 2, j will move to the left till reaches 1. but i will always be at 2, because this condition never comes true:while (a[i]<x) i++
• tucuxi: With that array, i and j will originally be 0 and 6, and when the if is reached, will be 0 and 4; since 0 <= 4, these indices will be swapped, yielding {1,3,4,7,2,8,9}. The next time around the loop, i and j will start at 1 and 3, and will end the loop, without performing any swaps, with i=1. As expected, all elements in the sub-array {1} are smaller than those in sub-array {3,4,7,2,8,9}. Where is the problem?

Answer 2

It seem that the algorithm (as taken from "Introduction to algorihtm 3rd ed") can be implemented as follows (C++) should be similar in Java`s generics:

template <typename T> void swap_in_place(T* arr, int a, int b)
{
 T tmp = arr[a];
 arr[a] = arr[b];
 arr[b] = tmp;
}
template <typename T> int partition(T* arr, int l, int r)
{
 T pivot = arr[r];
 int i = l-1;
 int j;
 for(j=l; j < r; j++) {
 if (arr[j] < pivot /* or cmp callback */) {
 // preincrement is needed to move the element
 swap_in_place<T>(arr, ++i, j);
 }
 }
 // reposition the pivot
 swap_in_place(arr, ++i, j);
 return i;
 }
template <typename T> void qsort(T* arr, int l, int r) 
{
 if ( l < r ) {
 T x = partition<T>(arr, l, r);
 qsort(arr, l, x-1);
 qsort(arr, x+1, r);
 }
 }

However, its a simple pseudocode implementation, I dont know if it`s the best pivot to pick from. Maybe (l+r)/2 would be more proper.

Answer 3

Pretty simple solution with deque:

int [] arr = {3, 2, 5, 9, 6, 8};
Deque<Integer> q = new LinkedBlockingDeque<Integer>();
for (int t = 0; t < arr.length; t++) {
 if (t == 0) {
 q.add(arr[t]);
 continue;
 }
 if (arr[t] <= arr[0])
 q.addFirst(arr[t]);
 else
 q.addLast(arr[t]);
}
for (int t:q) {
 System.out.println(t);
}

Output is:

2
3
5 <-- pivot
9
6
8

• tucuxi: This is not a good idea - Quicksort can be efficiently implemented as an in-place sorting algorithm, with no extra memory required. You are using a complex data structure (the per-element of a your LinkedBlockingDeque is larger than 2 ints).
• Ian2thedv: @tucuxi I agree this is not a best solution, but I posted this answer due to its simple nature. However, I do not fully agree with your second statement, even though it is negligible, Quicksort does require additional amounts of memory O(logn)
• tucuxi: @lan2thedv O(logn) extra memory is nothing compared to your O(n logn) extra memory proposal. If we asume ints are the size of pointers, and you queue uses 2 pointers per element, your implementation would take 3*n extra space - and would have horrible memory locality to boot. If you're going to use extra memory because it is simple, at least use a plain array.

Answer 4

There is video that I made on Pivot based partition I explained both the methods of patitioning.

https://www.youtube.com/watch?v=356Bffvh1dA

And based on your(the other) approach

https://www.youtube.com/watch?v=Hs29iYlY6Q4

And for the code. This is a code I wrote for pivot being the first element and it takes O(n) Comparisons.

void quicksort(int a[],int l,int n)
{ 
 int j,temp;
 if(l+1 < n)
 {
 int p=l;
 j=l+1;
 for(int i=l+1;i<n;++i)
 {
 if(a[i]<a[p])
 {
 temp=a[i];
 a[i]=a[j];
 a[j]=temp;
 j++;
 }
 } 
 temp=a[j-1];
 a[j-1]=a[p];
 a[p]=temp;
 quicksort(a,l,j);
 quicksort(a,j,n);
 }
}

• CiaPan: Please check again your code. The recursive call quicksort(a,0,j); seems incorrect. BTW, that is not a partition method...
• CiaPan: How does your code work if a[0] is already the smallest item in the array?
• Anup: Ya its the whole quicksort code I wrote here. If you ignore the recursive call then it basically partitioning the array based on the first element.
• Anup: Then it will compare a[0] with all the elements j=1 and will remain 1. In the end a[0] and a[0] will be interchanged meaning nothing will be changed and the recursive call will be made to 0-1 and 1-n. as 0+1!<1 so the first one will return and the second one will go an sorting the rest of the array
• CiaPan: ...and then it will make a recursive call to quicksort(a,0,some_new_j) despite the fact the 0-th item does not belong to the rest of the array!

Answer 5

The partition function below works as follow:
 The last variable points to the last element in the array that has not
 been compared to the pivot element and can be swapped.
 If the element directly next to the pivot element is less than the pivot
element. They are swapped.
 Else if the pivot element is less than the next element, the next
element is swapped with the element whose index is the last variable.

static int partition(int[] a){
 int pivot = a[0]; 
 int temp, index = 0;
 int last = a.length -1;
 for(int i = 1; i < a.length; i++){
 //If pivot > current element, swap elements
 if( a[i] <= pivot){
 temp = a[i];
 a[i] = pivot;
 a[i-1] = temp; 
 index = i;
 } 
 //If pivot < current elmt, swap current elmt and last > index of pivot
 else if( a[i] > pivot && last > i){
 temp = a[i];
 a[i] = a[last];
 a[last] = temp;
 last -= 1;
 i--;
 }
 else
 break;
 }
 return index;
}