quick_sort.go

package main

import (
	"math/rand"
)

// QuickSort sorts the array using the quicksort algorithm
func QuickSort(arr []int, low, high int, metrics *Metrics) {
	if low < high {
		pi := randomizedPartition(arr, low, high, metrics)

		// Recursively sort elements before and after partition
		QuickSort(arr, low, pi-1, metrics)
		QuickSort(arr, pi+1, high, metrics)
	}
}

// randomizedPartition selects a random pivot and partitions the array
func randomizedPartition(arr []int, low, high int, metrics *Metrics) int {
	// Select a random pivot index
	pivotIndex := rand.Intn(high-low+1) + low

	arr[pivotIndex], arr[high] = arr[high], arr[pivotIndex]
	metrics.Swaps++

	return partition(arr, low, high, metrics)
}

// partition partitions the array around a pivot
func partition(arr []int, low, high int, metrics *Metrics) int {
	pivot := arr[high]
	i := low - 1

	for j := low; j < high; j++ {
		metrics.Comparison++
		if arr[j] <= pivot {
			i++
			// Swap arr[i] and arr[j]
			arr[i], arr[j] = arr[j], arr[i]
			metrics.Swaps++
		}
	}

	arr[i+1], arr[high] = arr[high], arr[i+1]
	metrics.Swaps++

	return i + 1
}