Back to Repositories

Testing QuickSort Algorithm Variants in hello-algo

A comprehensive test suite for validating QuickSort algorithm implementations in Go, covering standard QuickSort along with median pivot and tail recursion optimizations. The tests verify correct sorting behavior and optimization effectiveness across different input scenarios.

Test Coverage Overview

The test suite provides thorough coverage of three QuickSort variants: standard implementation, median pivot optimization, and tail recursion optimization.

Key functionality tested includes:

Basic QuickSort implementation with random pivot
Median-of-three pivot selection optimization
Tail recursion elimination for improved performance
Sorting behavior with duplicate elements

Implementation Analysis

The testing approach employs Go’s native testing package to validate sorting functionality across different QuickSort implementations. Each test case uses a consistent input array [4,1,3,1,5,2] to enable direct comparison between implementations.

Testing patterns include:

Structured test functions using Go’s testing.T framework
Direct output verification through fmt.Println
Consistent test data across variants for comparative analysis

Technical Details

Testing infrastructure includes:

Go testing package (testing)
fmt package for output verification
Custom QuickSort implementations (quickSort, quickSortMedian, quickSortTailCall)
Array-based test fixtures
Index-based partition handling

Best Practices Demonstrated

The test suite exemplifies several testing best practices in Go.

Notable practices include:

Isolated test functions for each implementation variant
Clear test function naming conventions
Consistent test data across implementations
Modular code organization with separate structs for each variant
Descriptive output messages for debugging

krahets/hello-algo

codes/go/chapter_sorting/quick_sort_test.go

            
// File: quick_sort_test.go
// Created Time: 2022-12-12
// Author: msk397 ([email protected])

package chapter_sorting

import (
	"fmt"
	"testing"
)

// 快速排序
func TestQuickSort(t *testing.T) {
	q := quickSort{}
	nums := []int{4, 1, 3, 1, 5, 2}
	q.quickSort(nums, 0, len(nums)-1)
	fmt.Println("快速排序完成后 nums = ", nums)
}

// 快速排序（中位基准数优化）
func TestQuickSortMedian(t *testing.T) {
	q := quickSortMedian{}
	nums := []int{4, 1, 3, 1, 5, 2}
	q.quickSort(nums, 0, len(nums)-1)
	fmt.Println("快速排序（中位基准数优化）完成后 nums = ", nums)
}

// 快速排序（尾递归优化）
func TestQuickSortTailCall(t *testing.T) {
	q := quickSortTailCall{}
	nums := []int{4, 1, 3, 1, 5, 2}
	q.quickSort(nums, 0, len(nums)-1)
	fmt.Println("快速排序（尾递归优化）完成后 nums = ", nums)
}