Quick sorting algorithm implemented by C++ and Go.

quick_sort.cpp

/*
 * @author  duruyao
 * @file    quick_sort.cpp
 * @desc
 * @date    2021-10-02
 * @version 1.0
 */

#include <vector>
#include <iostream>

/**
 * quickSort sorts data set by quick sorting algorithm.
 *
 * ---time complexity---
 *
 * best    case:    O(n * log n)
 * average case:    O(n * log n)
 * worst   case:    O(n ^ 2)
 *
 * ---when to use---
 *
 * (1) algorithm is required to perform well under average case.
 *
 * ---parameters and return---
 *
 * @tparam T        is a certain data type
 * @param input     is a data set to be sorted
 * @param begin     is the first index
 * @param end       is the index past the last index
 * @param cmpFunc   is a function for comparing elements of data set
 * @param pivotFunc is a function for finding pivot (default nullptr, set first element as pivot)
 */
template<typename T>
void quickSort(std::vector<T> &input, int begin, int end, int (*cmpFunc)(const T &, const T &),
               int (*pivotFunc)(std::vector<T> &, int, int, int(*)(const T &, const T &)) = nullptr) {
    if (end - begin <= 1) {
        return;
    }
    auto pivotIdx = pivotFunc ? pivotFunc(input, begin, end, cmpFunc) : begin;
    std::swap(input[begin], input[pivotIdx]);
    auto idx = begin + 1;
    for (auto i = idx; i < end; i++) {
        if (cmpFunc(input[i], input[begin]) < 0) {
            std::swap(input[i], input[idx]);
            idx++;
        }
    }
    idx--;
    std::swap(input[begin], input[idx]);
    quickSort(input, begin, idx, cmpFunc, pivotFunc);
    quickSort(input, idx + 1, end, cmpFunc, pivotFunc);
}

/**
 * medianOfRand3 selects a median element from random 3 elements.
 *
 * @tparam T        is a certain data type
 * @param input     is a data set
 * @param begin     is the first index
 * @param end       is the index past the last index
 * @param cmpFunc   is a function for comparing elements of data set
 * @return
 */
template<typename T>
int medianOfRand3(std::vector<T> &input, int begin, int end, int(*cmpFunc)(const T &, const T &)) {
    if (end - begin < 3) {
        return begin;
    }
    auto a = begin, b = (begin + end - 1) / 2, c = end - 1;
    if (cmpFunc(input[a], input[b]) > 0) {
        std::swap(input[a], input[b]);
    }
    if (cmpFunc(input[b], input[c]) > 0) {
        std::swap(input[b], input[c]);
    }
    if (cmpFunc(input[a], input[b]) > 0) {
        std::swap(input[a], input[b]);
    }
    return b;
}

int cmpInt(const int &n1, const int &n2) {
    return n1 - n2;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &input) {
    for (auto &it : input) { os << it << " "; }
    return os;
}

int main(int argc, char **argv) {
    std::vector<int> array;
    for (int i = 0; i < 40; array.push_back(random() % 100), i++);
    std::cout << array << std::endl;
    quickSort(array, 0, (int) array.size(), cmpInt, medianOfRand3);
    std::cout << array << std::endl;
    return 0;
}

quick_sort.go

package main

import (
	"fmt"
	"math/rand"
)

// QuickSort sorts data set by quick sorting algorithm.
//
// ---time complexity---
//
// best    case:    O(n * log n)
// average case:    O(n * log n)
// worst   case:    O(n ^ 2)
//
// ---when to use---
//
// (1) algorithm is required to perform well under average case.
//
// ---parameters and return---
//
// @param input     is a data set to be sorted
// @param cmpFunc   is a function for comparing elements of data set
// @param pivotFunc is a function for finding pivot (if pivotFunc[0] is nullptr, set first element as pivot)
//
func QuickSort(input []interface{}, cmpFunc func(interface{}, interface{}) int,
	pivotFunc ...func([]interface{}, func(interface{}, interface{}) int) int) {
	if len(input) <= 1 {
		return
	}
	pivot := 0
	if len(pivotFunc) > 0 && pivotFunc[0] != nil {
		pivot = pivotFunc[0](input, cmpFunc)
		input[0], input[pivot] = input[pivot], input[0]
	}
	idx := 1
	for i := idx; i < len(input); i++ {
		if cmpFunc(input[i], input[0]) < 0 {
			input[idx], input[i] = input[i], input[idx]
			idx++
		}
	}
	idx--
	input[idx], input[0] = input[0], input[idx]
	QuickSort(input[:idx], cmpFunc, pivotFunc...)
	QuickSort(input[idx+1:], cmpFunc, pivotFunc...)
}

func MedianOfRand3(input []interface{}, cmpFunc func(interface{}, interface{}) int) int {
	if len(input) < 3 {
		return 0
	}
	a, b, c := 0, (len(input)-1)/2, len(input)-1
	if cmpFunc(input[a], input[b]) > 0 {
		input[a], input[b] = input[b], input[a]
	}
	if cmpFunc(input[b], input[c]) > 0 {
		input[b], input[c] = input[c], input[b]
	}
	if cmpFunc(input[a], input[b]) > 0 {
		input[a], input[b] = input[b], input[a]
	}
	return b
}

func CmpInt(n1 interface{}, n2 interface{}) int {
	return n1.(int) - n2.(int)
}

func main() {
	var input []interface{}
	for i := 0; i < 40; i++ {
		input = append(input, rand.Int()%100)
	}
	fmt.Println(input)
	QuickSort(input, CmpInt, MedianOfRand3)
	fmt.Println(input)
}