<commit_before>package gosort

import (
    "math/rand"
    "time"
)

// The private initialisation function for this source file
func init() {
    // Seed the RNG ready for use for randomly selecting pivots
    rand.Seed(time.Now().UTC().UnixNano())
}

/*
 ChoosePivot defines the signature for a function that given a slice returns
 an index that can be used a pivot in the partitioning stage of QuickSort
 algorithm.
 */
type ChoosePivot func(a []int) int

/*
 QuickSort sorts an array of integers, in place, using the QuickSort
 algorithm.
 This implementation uses random pivot selection.
 */
func QuickSort(a []int) {
    QuickSortWithPivotChoice(a, ChooseRandomElementPivot)
}

/*
 QuickSortWithPivotChoice sorts an array of integers, in place, using the
 QuickSort algorithm, but also allows calling code to select how pivots
 are chosen. Pass one of the Choose<strategy>Pivot functions as the
 second argument to specify a pivot selection strategy.
 */
func QuickSortWithPivotChoice(a []int, choosePivot ChoosePivot) {
    if len(a) <= 1 {
        return
    }

    pivot := choosePivot(a)
    pivot = partition(a, pivot)
    QuickSortWithPivotChoice(a[:pivot], choosePivot)
    QuickSortWithPivotChoice(a[pivot+1:], choosePivot)
}

// A pivot selection strategy: choose the first element
func ChooseFirstElementPivot(a []int) int {
    return 0
}

// A pivot selection strategy: choose the last element
func ChooseLastElementPivot(a []int) int {
    return len(a) - 1
}

// A pivot selection strategy: choose the middle element
func ChooseMiddleElementPivot(a []int) int {
    return (len(a) - 1) / 2
}

// A pivot selection strategy: choose a random element
func ChooseRandomElementPivot(a []int) int {
    return rand.Intn(len(a))
}

/*
 A pivot selection strategy: try to choose a median-ish element.
 
 First selects the first, middle and last elements, then chooses
 the median of these three values and returns its index.<commit_msg>Clarify the intent of the pivot selection strategies<commit_after>package gosort

import (
    "math/rand"
    "time"
)

// The private initialisation function for this source file
func init() {
    // Seed the RNG ready for use for randomly selecting pivots
    rand.Seed(time.Now().UTC().UnixNano())
}

/*
 ChoosePivot defines the signature for a function that given a slice returns
 an index that can be used a pivot in the partitioning stage of QuickSort
 algorithm.
 */
type ChoosePivot func(a []int) int

/*
 QuickSort sorts an array of integers, in place, using the QuickSort
 algorithm.
 This implementation uses random pivot selection.
 */
func QuickSort(a []int) {
    QuickSortWithPivotChoice(a, ChooseRandomElementPivot)
}

/*
 QuickSortWithPivotChoice sorts an array of integers, in place, using the
 QuickSort algorithm, but also allows calling code to select how pivots
 are chosen. Pass one of the Choose<strategy>Pivot functions as the
 second argument to specify A QuickSort pivot selection strategy.
 */
func QuickSortWithPivotChoice(a []int, choosePivot ChoosePivot) {
    if len(a) <= 1 {
        return
    }

    pivot := choosePivot(a)
    pivot = partition(a, pivot)
    QuickSortWithPivotChoice(a[:pivot], choosePivot)
    QuickSortWithPivotChoice(a[pivot+1:], choosePivot)
}

// A QuickSort pivot selection strategy: choose the first element. Use with
// QuickSortWithPivotChoice.
func ChooseFirstElementPivot(a []int) int {
    return 0
}

// A QuickSort pivot selection strategy: choose the last element. Use with
// QuickSortWithPivotChoice.
func ChooseLastElementPivot(a []int) int {
    return len(a) - 1
}

// A QuickSort pivot selection strategy: choose the middle element. Use with
// QuickSortWithPivotChoice.
func ChooseMiddleElementPivot(a []int) int {
    return (len(a) - 1) / 2
}

// A QuickSort pivot selection strategy: choose a random element. Use with
// QuickSortWithPivotChoice.
func ChooseRandomElementPivot(a []int) int {
    return rand.Intn(len(a))
}

/*
 A QuickSort pivot selection strategy: try to choose a median-ish element.
 Use with QuickSortWithPivotChoice.
 
 First selects the first, middle and last elements, then chooses
 the median of these three values and returns its index.
{'fraction_non_alphanumeric': 0.0799713535449988, 'fraction_numerical': 0.0028646455001193603, 'mean_word_length': 3.970344009489917, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2676066', 'n_tokens_mistral': 1238, 'n_tokens_neox': 1184, 'n_words': 481}