Quick Sort is an efficient, recursive sorting algorithm that uses the divide-and-conquer approach. The basic idea is to select a ‘pivot’ element from the array and partition the other elements into two sub-arrays according to whether they are less than or greater than the pivot.

Algorithm Steps

1. If the array has 1 or 0 elements, it is already sorted.
2. Choose a pivot element from the array.
3. Partition the array into two halves:
   • Elements less than the pivot.
   • Elements greater than the pivot.
4. Recursively apply the above steps to the sub-arrays.

Go Implementation

package main

import "fmt"

// quickSort function sorts an array using the Quick Sort algorithm
func quickSort(arr []int) []int {
    if len(arr) < 2 {
        return arr // Base case: arrays with 0 or 1 element are already sorted
    }

    // Choose the pivot (we can use the last element as the pivot)
    pivot := arr[len(arr)-1]

    // Create two slices for the partitions
    less := []int{}
    greater := []int{}

    // Partitioning step
    for _, value := range arr[:len(arr)-1] {
        if value <= pivot {
            less = append(less, value) // Elements less than or equal to pivot
        } else {
            greater = append(greater, value) // Elements greater than pivot
        }
    }

    // Recursively apply quickSort to the partitions and combine
    return append(append(quickSort(less), pivot), quickSort(greater)...)
}

func main() {
    // Example usage
    arr := []int{7, 2, 1, 6, 8, 5, 3, 4}
    fmt.Println("Original array:", arr)
    sortedArr := quickSort(arr)
    fmt.Println("Sorted array:", sortedArr)
}

Explanation of the Code

The Go program consists of the following parts:

• Package Declaration: We start with package main which defines the entry point of the program.
• Import Statement: The fmt package is imported for input and output functions.
• quickSort Function: This function performs the sorting. It checks if the array has fewer than two elements and returns it if true. It then selects the last element as the pivot and partitions the array into two slices.
• Recursion: The function calls itself for the less and greater partitions and combines the sorted slices.
• main Function: This is the entry point where an example array is defined, and the quickSort function is called. The original and sorted arrays are printed.

Conclusion

Quick Sort is a highly efficient sorting algorithm and is widely used in practice. The Go implementation provided above demonstrates how to apply the Quick Sort algorithm effectively.