'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!
Solution 1:[1]
https://www.youtube.com/watch?v=COk73cpQbFQ 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;
}
https://www.youtube.com/watch?v=6UHCG64tHgo 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);
}
}
Solution 2:[2]
/* 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:-http://www.liladharpaliwal.blogspot.in/
Solution 3:[3]
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);
}
}
Solution 4:[4]
Try this algo: https://www.youtube.com/watch?v=7h1s2SojIRw
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);
}
Solution 5:[5]
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);
}
Solution 6:[6]
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
Solution 7:[7]
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);
}
Solution 8:[8]
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;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | buzzbox |
| Solution 2 | |
| Solution 3 | Kumar Anil Chaurasiya |
| Solution 4 | saran3h |
| Solution 5 | Baiyan Huang |
| Solution 6 | Pang |
| Solution 7 | quark |
| Solution 8 | user830818 |