Quicksort with first element as pivot example

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: 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);
 }

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);
}