GO Program to Implement Quick Sort

For a better understanding of this example, we always recommend you to learn the basic topics of Golang programming listed below:

Here we are explaining how to write a GO program to sort a list of elements from an array. There are different types of sorting algorithms. In this case, we use a Quick Sort for sorting array elements. Quicksort is one of the most efficient sorting algorithms which is commonly used in production sorting implementations. As the name implies, we can say it is the fastest sorting algorithm, but you should give attention and care to the sorting implementation otherwise your speed can drop quickly. So it's not an efficient algorithm for large data sets.

 It works on the principle of the divide and conquers class of algorithms. Here it divides an array into smaller chunks which will help you to sort elements fast and easily.

Here we use a specified value is called a pivot. A large unsorted array is partitioned into two sub-arrays based on the pivot position.  One of the arrays holds values smaller than the pivot value, based on which the partition is made and another array holds values greater than the pivot value. Then perform the sort operation recursively on both sides of the pivot till there are no more sub-arrays existing.

How to Implement Quick Sort

In this GO program, we accept the user's values using the 'fmt.scanln()'  and 'fmt.println()'  methods which are defined under the fmt package. In order to use these functions, we need to import the “fmtpackage. To convert string type into int type, we use Atoi() function which is equivalent to ParseInt(str string, base int, bitSize int). You need to import the "strconv" Package in your program to access Atoi() function.

Here variable A holds the array elements. Other variables n and pivot are used as the size of the array and pivot index element respectively. Use for loop to read array elements. Use two variables low and high to store the lowest and highest index position except for the pivot element. Quick Sort algorithm is developed using the divide and conquer approach and it works under the comparison algorithm category.

Here we mainly use two functions, the main quickSort() function as well as the partition() function. The partition() function is used to find the pivot value and is responsible for moving everything to the correct side of the pivot. The quickSort() function is used to handle the recursive nature of the algorithm.

Time Complexity:
  • Best complexity: n*log(n)
  • Average complexity: n*log(n)
  • Worst complexity: n^2

Given below are the steps which are used in the Go program to implement QuickSort.

ALGORITHM

STEP 1: Import the packages 'fmt' and 'strconv'
STEP 2: Open the main() to start the program, GO program execution starts with the main()
STEP 3: Declare the variable n.
STEP 4: Read the size of the array as n
STEP 5: Define the array A[]
STEP 6: Read the A[] array elements by using a 'for loop'.
STEP 7: Perform quick sort by calling function quickSort(arr, 0, len(arr) - 1)
STEP 8: Use for loop to display sorted array.
STEP 9: Exit

Steps To Implement quickSort(arr, 0, len(A) – 1)

STEP 1: Check if low < high, then find the pivot index of a lower bound of an array by calling partition(A, low, high)
STEP 2: Apply Divide and conquer strategy to sort the left side array respective to the pivot position  by calling quickSort(A, low, pivot)
STEP 3: Sort the right side array respective to the pivot position  by calling quickSort(A, pivot + 1, high)

Steps To Implement  partition(A []int, low, high int)

STEP 1: Pick a lowest bound element as a pivot value pivot
STEP 2: Declare two variables low and high (i.e. pointer) to store the lowest and highest index position except for the pivot element.
STEP 3: Assign i=low, j=high.
STEP 4: Using for loop, move the left side pointer towards the right by incrementing the index value of 'i' until the value of the pointer A[i]  is less than or equal to the pivot element.
STEP 5: Using for loop, move the right side pointer towards the left by decrementing the index value of 'j' until the value of the pointer is greater than the pivot element.
STEP 6: Interchange the values of the present in the index i and j of an array only if i is less than j
STEP 7: Interchange the element in j'th position to the lower bound of an array and place the Pivot element to the j's position
STEP 8: Finally return the appropriate index position of the pivot element
 

GO Source Code

                                          package main

import (
 "fmt"
 "strconv"
)

func quickSort(A []int, low, high int) {
 if low < high {

        // Find the pivot index of an lower bound of an array
  var pivot = partition(A, low, high)

        // Apply Divide and conquer strategy
        // to sort the left side and right side of an array
        // respective to the pivot position

        // Left hand side array
  quickSort(A, low, pivot)

        // Right hand side array
  quickSort(A, pivot + 1, high)
 }
}

func partition(A []int, low, high int) int {

    // Pick a lowest bound element as an pivot value
 var pivot = A[low]

 var i = low
 var j = high

 for i < j {

        // Increment the index value of "i"
        // till the left most values should be less than or equal to the pivot value
  for A[i] <= pivot && i < high {
   i++;
  }

        // Decrement the index value of "j"
        // till the right most values should be greater than to the pivot value
  for A[j] > pivot && j > low {
   j--
  }

        // Interchange the values of present 
        // in the index i and j of an array only if i is less than j
  if i < j {
   var temp = A[i]
   A[i] = A[j]
   A[j] = temp
  }
 }

    // Interchange the element in j's poisition to the lower bound of an array
    // and place the Pivot element to the j's position
 A[low] = A[j]
 A[j] = pivot

    // Finally return the appropriate index position of the pivot element
 return j
}

func main() {

 fmt.Println("Enter the size of the array")
 var n int
 fmt.Scan(&n)
 A := make([]int, n, 100)
fmt.Println("Enter elements : ")

 for i := 0; i < n; i++ {
  fmt.Scan(&A[i])
 }


 quickSort(A, 0, len(A) - 1)
 fmt.Print("After Sorting: ")
 for i := 0; i < n; i++ {
  fmt.Print(strconv.Itoa(A[i]) + " ")
 }
}

                                      

OUTPUT

Enter the size of the array
5
Enter elements: 
81
60
73
52
95
After Sorting: 52 60 73 81 95