Go – Quick Sort

In this tutorial, we will learn how to implement the Quick Sort algorithm using the Go programming language (Golang).

Quick Sort is a divide-and-conquer sorting algorithm that partitions the list into two sublists, one with elements smaller than a pivot and the other with elements larger than the pivot. It then recursively sorts the sublists. Quick Sort is efficient and widely used in practice, with an average-case time complexity of \( O(n \log n) \).

We will go through a detailed explanation and a program to implement Quick Sort in Go.

Logic of Quick Sort

The Quick Sort algorithm involves the following steps:

  1. Choose a Pivot: Select an element from the list to act as the pivot.
  2. Partition the List: Rearrange the list such that all elements smaller than the pivot are on the left and all elements larger than the pivot are on the right.
  3. Recursively Sort Sublists: Recursively apply the same process to the left and right sublists.
  4. Combine Results: Combine the sorted sublists and the pivot to produce the final sorted list.

Quick Sort has a worst-case time complexity of \( O(n^2) \) when the pivot is poorly chosen, but this can be mitigated by choosing a random or median pivot.

Example Program for Quick Sort

Program – quick_sort.go

</>
Copy
package main

import "fmt"

// Function to partition the array
func partition(arr []int, low, high int) int {
    pivot := arr[high] // Choose the last element as pivot
    i := low - 1       // Index of smaller element

    for j := low; j < high; j++ {
        // If current element is smaller than or equal to the pivot
        if arr[j] <= pivot {
            i++
            // Swap arr[i] and arr[j]
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    // Swap arr[i+1] and the pivot element
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

// Function to implement Quick Sort
func quickSort(arr []int, low, high int) {
    if low < high {
        // Partition the array
        pi := partition(arr, low, high)

        // Recursively sort the sublists
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

func main() {
    // Input array
    arr := []int{10, 7, 8, 9, 1, 5}

    // Display the original array
    fmt.Println("Original array:", arr)

    // Sort the array using Quick Sort
    quickSort(arr, 0, len(arr)-1)

    // Display the sorted array
    fmt.Println("Sorted array:", arr)
}

Explanation of Program

  1. Partition Function: The partition function selects the last element as the pivot and rearranges the array such that all elements smaller than or equal to the pivot are on the left, and all larger elements are on the right. The pivot is then placed in its correct position.
  2. Quick Sort Function: The quickSort function recursively sorts the left and right sublists around the pivot.
  3. Base Case: The recursion stops when the sublist has one or no elements, as it is already sorted.
  4. Input and Output: The original and sorted arrays are displayed using fmt.Println.

Output

This program demonstrates the Quick Sort algorithm, which efficiently sorts elements by recursively partitioning and rearranging them around a pivot.