Sorting Algorithms in Go : Quick Sort

Quick sort is a popular sorting algorithm that works by selecting a “pivot” element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

The elements which are less than the pivot are placed in the left and the elements which are greater than or equal to the pivot are placed in the right.

The left side and right side elements are than divided into sub arrays then the sub-arrays are sorted recursively using the same process.

Here is a simple example of how quick sort works:

• Given the array [5, 2, 6, 3, 1, 4], the pivot element is chosen as the middle element (in this case, 3).

• The elements in the array are partitioned into two sub-arrays:
• [2, 1] (elements less than 3) and [5, 6, 4] (elements greater than or equal to 3).

The two sub-arrays are then sorted recursively using the same process :

• [ 2, 1 ] becomes the array, and the pivot element is chosen as 2.

The elements in the array are partitioned into two sub-arrays:

• [ 1 ] (elements less than 2) and [ 2 ] (elements greater than or equal to 2).

Now the left side elements are sorted.

Again [5, 6, 4] becomes an another array, and here the pivot element is chosen as 5.

The elements in the array are partitioned into two sub-arrays :

• [ 4 ] (elements less than 5) and [ 6 ] (elements greater than or equal to 5).

The sorted sub-arrays are then combined : [ 1, 2, 3, 4, 5, 6 ]

Here is a simple implementation of quick sort in Go:

package main

import "fmt"

func quickSort(arr []int) []int {
  // If the input array has less than 2 elements,
 // it is already sorted, so return it as is.
 if len(arr) < 2 {
  return arr
 }

 // Here we are chosing the pivot element
 // as the middle element of the array.
 pivotIndex := len(arr) / 2
 pivot := arr[pivotIndex]

  // Initialize two slices to hold the elements that are 
  // less than and greater than the pivot.
 var less []int
 var greater []int

  // Iterate through the input array and partition
 // the elements into the appropriate slice.
 for i, v := range arr {

// Skip the pivot element, since it will be added back in later.
  if i != pivotIndex {

// If the element is less than the pivot, add it to the "less" slice.
// If the element is greater than or equal to the pivot,
// add it to the "greater" slice.
   if v < pivot {
    less = append(less, v)
   } else {
    greater = append(greater, v)
   }
  }
 }

  // Recursively sort the "less" and "greater" slices,
  // then append the pivot element and return the result.
 
 sortedLess := quickSort(less)
 sortedGreater := quickSort(greater)
 sorted := append(sortedLess, pivot)
 sorted = append(sorted, sortedGreater...)

 return sorted
}

func main() {
 arr := []int{5, 2, 6, 3, 1, 4}  // Initialize the input array.
 fmt.Println(quickSort(arr))  // Sort the array and print the result.
}

Best Case Scenario of Quick Sort -

The time complexity of quick sort in the Best case scenario is : O(n*logn).

It occurs when the pivot element is chosen such that it results in the most balanced partition possible. This means that the lengths of the two sub-arrays are as close as possible to each other.

Average Case Scenario of Quick Sort -

The time complexity of quick sort in the Average case scenario is : O(n*logn).

It occurs when the pivot element is chosen randomly and the pivot element is resulted in a fairly balanced partition.

Worst Case Scenario of Quick Sort -

The time complexity of quick sort in the Worst case scenario is : O(n²).

The worst case for quick sort occurs when the pivot element is chosen poorly, resulting in one sub-array being much larger than the other.

Thanks for reading. See you in the next article :)

Reach me on 📱-

https://www.linkedin.com/in/saeeed/

https://twitter.com/saeed0x1