Quick Sort Algorithm implementation in java and Golang

Step 1:

[ 10 , 8 , 7 , 5 , 6 ]

Pivot = 6 , low = 0, high = 6, i = 0

Iterate from left to right and look for the element smaller than pivot

Step 2:

[ 5 , 8 , 7, 10 , 6 ]

Pivot = 6 , low = 0, high = 6, i = 1

4th element was smaller than pivot, so 4th element is replaced with ith element (ith element was 10, jth element was 5). After the process I is incremented.

Step 3:

[ 5 , 6 , 7 , 10 , 8 ]

Pivot = 6, low = 0, high = 6, i = 1

Continue the step 2 till the left side of is smaller than pivot. Once it is achieved, replace ith element with pivot element.

After this step, left side of pivot element will be lesser than pivot and right side of pivot will be bigger than pivot.

Step 4:

[ 5 , 6 , 7 , 10 , 8 ]

Divide the array from the index of pivot (which is 1 here)

Now repeat the process from new split sub arrays.

Indexes will be [0 ti (i-1)] and [(i+1) to arr.length -1]

Continue the steps from Step 1 to Step 4 till low not greater than high.

File: QuickSort.go

package main
import "fmt"
func swap(arr []int, i, j int){
  tmp := arr[i]
  arr[i] = arr[j]
  arr[j] = tmp
}
func partition(arr []int, low, high int) int{
  pivot := arr[high]
  i := low
  for j:= low ; j < high; j++ {
    if (pivot > arr[j]){
      swap(arr, i, j)
      i++
    }
  }
  swap(arr, i, high)
  return i
}
func sort(arr []int, low, high int) {
  if (low < high){
    pi := partition(arr, low, high)
    sort(arr, low, pi -1)
    sort(arr, pi + 1, high)
  }
}
func main(){
  arr := []int{45,34,23,46,78}
  sort(arr, 0, len(arr) -1)
  fmt.Println("Sorted arrays : ", arr)
}

File: QuickSort.java

import java.util.*;
public class QuickSort {
    public static void main(String[] args){
        int[] arr = new int[]{34,12,23,78,56};
        QuickSort q = new QuickSort();
        q.sort(arr, 0, arr.length -1);
        System.out.println(“Sorted : “ + Arrays.toString(arr));
    }
    void sort(int[] arr, int low, int high){
        if(low < high){
            int p = partition(arr, low, high);
            sort(arr, low, p -1);
            sort(arr, p+1, high);
        }
    }
    int partition(int[] arr, int low, int high){
        int pivot = arr[high];
        int i = low;
        for (int j = low; j < high; j++){
            if (arr[j] < pivot){
                swap(arr, i++, j);
            }
        }
        swap(arr, i, high);
        return i;
    }
    void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}