QuickSort Program

QuickSort:

[5,9,3,15,13,7,1,8,18,14,4]

Steps:

we will choose first element as pivot
move all less than pivot on one side and other on one side

so we need to find the pivot element position
then partition in 2 parts first is before pivot and other is after pivot

public class QuickSort {
   
    public static void main(String args[]) {
        int arr[] = {10,3,16,8,9,1,15,6,18};
        quick_sort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
   
    static void quick_sort ( int A[ ] ,int start , int end ) {
           if( start < end ) {
                //stores the position of pivot element
                 int piv_pos = partition (A,start , end ) ;    
                 quick_sort (A,start , piv_pos -1);    //sorts the left side of pivot.
                 quick_sort ( A,piv_pos +1 , end) ; //sorts the right side of pivot.
           }
        }
   
    static int partition ( int A[],int start ,int end) {
        int i = start + 1;
        int piv = A[start] ;            //make the first element as pivot element.
        for(int j =start + 1; j <= end ; j++ )  {
        /*rearrange the array by putting elements which are less than pivot
           on one side and which are greater that on other. */

              if ( A[ j ] < piv) {
                     swap (A ,i , j );
                i += 1;
            }
       }
       swap ( A,start ,i-1  ) ;  //put the pivot element in its proper place.
       return i-1;                      //return the position of the pivot
    }
   
    public static void swap(int[] A,int first, int second) {
        int temp = A[first];
        A[first] = A[second];
        A[second] = temp;
    }
   
}


How partition work in above:
start = 0 , end = 10
[5,9,3,15,13,7,1,8,18,14,4]
piv = A[start] = 5
i = start+1 = 1;
loop--> j=start+1 to <=end and j++

first round of loop:  a[j]>piv so nothing change
                                  i= 1, j=2
second round of loop: a[j]<piv so swap i with j and increase i by1
  [5,3,9,15,13,7,1,8,18,14,4]
       i = 2, j=3
third round of loop:  a[j]>piv so nothing change
i=2,j=4 
fourth round of loop:  a[j]>piv so nothing change
i=2,j=5
fifth round of loop:  a[j]>piv so nothing change
i=2,j=6
seventh round of loop: a[j]<piv so swap i with j and increase i by1
  [5,3,1,15,13,7,9,8,18,14,4]
       i = 3, j=7
next few round no change till i=3, j=9
in last round i=3,j=10
a[j]<piv so swap i with j and increase i by1
  [5,3,1,4,13,7,9,8,18,14,15]
       i = 4


now loop break move pivot element to actual position
swap i-1 with start(pivot)

now pivot moved to actual postion

then we will sort the leftside of pivot and right side