Quicksort with first element as pivot example

I am currently studying quicksort and would like to know how it works when the first (or last) element is chosen as the pivot point.

Say for example I have the following array:

{15, 19, 34, 41, 27, 13, 9, 11, 44} 

This is what I think happens:

{15, 19, 34, 41, 27, 13, 9, 11, 44} ^ pivot {15, 19, 34, 41, 27, 13, 9, 11, 44} ^ ^ compare these two, they are good {15, 19, 34, 41, 27, 13, 9, 11, 44} ^ ^ compare these two and swap {11, 19, 34, 41, 27, 13, 9, 15, 44} ^ ^ compare these two and swap {9, 19, 34, 41, 27, 13, 11, 15, 44} ^ ^ compare these two, they are good {9, 19, 34, 41, 27, 13, 11, 15, 44} ^ ^ compare these two, they are good {9, 19, 34, 41, 27, 13, 11, 15, 44} ^ ^ compare these two, they are good {9, 19, 34, 41, 27, 13, 11, 15, 44} ^ ^ compare these two, they are good {9, 19, 34, 41, 27, 13, 11, 15, 44} ^ ^ compare these two, they are good {9, 19, 34, 41, 27, 13, 11, 15, 44} End of first partition 

Is this how it works? If so, would 19 be the new pivot point, or do you divide the array in half to find it (so that it would be 27/13), or does it depend on the implementation of the quicksort? Thanks for your time!

9 Answers

Check wikipedia, there is a little example with a bit smaller list of inplace quicksort

With your example the idea is to partition

{15, 19, 34, 41, 27, 13, 9, 11, 44} 

into

{13, 9, 11 -- 15 -- 19, 34, 41, 27, 44} 

So first we move pivot to the end

Swap 44, and 15 {44, 19, 34, 41, 27, 13, 9, 11, 15} ^ ^ Than check 44, its larger than pivot, so swap with one one before last... {11, 19, 34, 41, 27, 13, 9, 44, 15} ^ ^ than check element at some position as last one was larger than pivot. 9 < 15, so proceed to the next, 19 > 15 => swap {11, 9, 34, 41, 27, 13, 19, 44, 15} ^ ^ swap again {11, 9, 13, 41, 27, 34, 19, 44, 15} ^ ^ next {11, 9, 13, 41, 27, 34, 19, 44, 15} ^ ^ and second last swap {11, 9, 13, 27, 41, 34, 19, 44, 15} ^ Now as forward and backward indices reached each other, we swap pivot into right position {11, 9, 13, 15, 41, 34, 19, 44, 27} 

And we got partitioned set. Items less than 15 at the beginning, than pivot = 15, and then greater elements.

EDIT: algorithm described in wikipedia article is a bit different:

Legend: ^ = storeindex # = i {44, 19, 34, 41, 27, 13, 9, 11, 15} ^# {44, 19, 34, 41, 27, 13, 9, 11, 15} ^ # ... until ... {44, 19, 34, 41, 27, 13, 9, 11, 15} ^ # {13, 19, 34, 41, 27, 44, 9, 11, 15} ^ # {13, 9, 34, 41, 27, 44, 19, 11, 15} ^ # {13, 9, 11, 41, 27, 44, 19, 34, 15} ^ # {13, 9, 11, 15, 27, 44, 19, 34, 41} ^- pivot 

for last element as pivot

int partition(int *a,int start,int end) { int pivot=a[end],temp,p1=start,i; for(i=start;i<end;i++) { if(a[i]<pivot) { if(i!=p1) { temp=a[p1]; a[p1]=a[i]; a[i]=temp; } p1++; } } temp=a[p1]; a[p1]=a[end]; a[end]=temp; return p1; } 

for first element as pivot

 int partition1(int *a,int start,int end) { int pivot=a[start],p1=start+1,i,temp; for(i=start+1;i<=end;i++) { if(a[i]<pivot) { if(i!=p1) { temp=a[p1]; a[p1]=a[i]; a[i]=temp; } p1++; } } a[start]=a[p1-1]; a[p1-1]=pivot; return p1-1; } void quicksort(int *a,int start,int end) { int p1; if(start<end) { p1=partition(a,start,end); quicksort(a,start,p1-1); quicksort(a,p1+1,end); } } 

/* Quick Sort taking first element as pivot element*/ void QuickSort(int* arr,int start,int last) { int i=start+1,j=last,temp; if(i>j) return; while(i<=j) { if(arr[i]<arr[start]) {enter code here i++; } if(arr[j]>arr[start]) { j--; } if(i<=j) { temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } temp=arr[start]; arr[start]=arr[j]; arr[j]=temp; QuickSort(arr,start,j-1); QuickSort(arr,j+1,last); } 

for whole code visit:-

Choosing the first element as a pivot...

class QuickSortPart1{ public int partition(int[] a, int left, int right) { int pivot = a[left]; while(left<=right) { while(a[left] < pivot) left++; while(a[right] > pivot) right--; if(left<=right) { int tmp = a[left]; a[left] = a[right]; a[right] = tmp; left++; right--; } } return left; } public void recursiveQuickSort(int[] a, int i, int j) { int idx = partition(a, i, j); if(i < idx-1) { recursiveQuickSort(a, i, idx-1); } if(j > idx) { recursiveQuickSort(a, idx, j); } } void printarray(int arr[]){ int len = arr.length; for(int i=0; i<len; i++) System.out.print(arr[i]+" "); } public static void main(String[] args) { int arr[] = new int[]{5,8,1,3,7,9,2}; System.out.print(arr[i]+" "); System.out.println("\n"); QuickSortPart1 ob = new QuickSortPart1(); ob.recursiveQuickSort(arr, 0, arr.length-1); ob.printarray(arr); } } 

Try this algo:

Base idea: All elements to left are smaller than all elements to the right then the element is said to be in 'sorted' position.

Algo:

// partition Partition(l,h) { pivot = A[l]; i=l; j=h; while(i<j) { do { i++; } while(A[i]<=pivot); do { j--; } while(A[j]>pivot); if(i<j) { swap(i,j); } } swap(A[l], A[j]); return j; } // quicksort QuickSort(l,h) { pi = Partition(l, h); QuickSort(l, pi); QuickSort(pi+1, h); } 

This is an example of quick sort that 2 pointers from start and end converging to the middle, while comparing & swapping, using first element as pivot - it is a different approach from the one introduced in Introduction to Algorithms

void quick_sort(vector<int>& vs, int l, int r) { if(l >= r) return; // recursion end condition int pivot = vs[l]; int first=l, last=r; while(first < last) { while(first < last && vs[last] > pivot) --last; vs[first] = vs[last]; while(first < last && vs[first] <= pivot) ++first; vs[last] = vs[first]; } vs[first] = pivot; // first is the final index for pivot quick_sort(vs, l, first); quick_sort(vs, first+1, r); } 

import java.security.SecureRandom; public class QuickSort { static int ArraySize = 35; public static void main(String[] args) { SecureRandom generator = new SecureRandom(); int[] array = generator.ints(ArraySize ,1,191).toArray(); QuickSort qs = new QuickSort(); qs.displayArray(array); int last = array.length-1; qs.quickSortHelper(array, 0, last); qs.displayArray(array); }//end method main public void quickSortHelper(int[] array, int starting, int ending){ int partPos = partition(array, starting, ending); if(partPos-1 > starting) { quickSortHelper(array, starting, partPos-1); } if(partPos < ending) { quickSortHelper(array, partPos, ending); } }//end method quickSortHelper public int partition(int[] array, int lSide, int rSide){ int partingVal = array[lSide]; do { for (;array[rSide] > partingVal; rSide--){} for (;array[lSide] < partingVal; lSide++){} if(rSide>=lSide) { int tempIndex = array[lSide]; array[lSide] = array[rSide]; array[rSide] = tempIndex; rSide--; lSide++; } }while(lSide<=rSide); return lSide; }//end method partitioin public void displayArray(int[] array){ for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); } System.out.println(""); }//end method displayArray }//end class QuickSort 

I found this easier to understand:

template <typename T> unsigned int partition(T* input, unsigned int first, unsigned int last) { T pivot = input[first]; auto partitionIndex = first; // search for first position for partition index for(auto i=first; i<=last; ++i){ if(input[i]>pivot){ partitionIndex = i; break; } } for(auto i = partitionIndex; i<=last; ++i){ if(input[i] <= pivot){ std::swap(input[i],input[partitionIndex]); ++partitionIndex; } } std::swap(input[first],input[partitionIndex-1]); return partitionIndex-1; } template <typename T> void quick_sort(T* input, unsigned int first, unsigned int last) { if(first>=last) return ; auto divide_point = partition(input, first, last); quick_sort(input, first, divide_point-1); quick_sort(input, divide_point+1, last); } 

the following code uses first element as pivot public static int[] qs(int[] list, int start, int end) { if (end - start <= 1) { return list; } int pivot = split(list, start, end); qs(list, start, pivot); qs(list, pivot + 1, end); return list; } private static int split(int[] list, int start, int end) { int pivot = list[start]; int i = start; for (int j = start + 1; j <= end; j++) { int current = list[j]; if (current < pivot) { swap(list, i + 1, j); i++; } } swap(list, start, i); return i; } private static void swap(int[] list, int i, int j) { int temp = list[i]; list[i] = list[j]; list[j] = temp; }