Algorithms and Data Structures - Quick Sort

This article was originally published on bmf-tech.com . Overview Referencing Algorithm Encyclopedia , we learn about algorithms and data structures. The implementation is also available on github - bmf-san/road-to-algorithm-master . Quick Sort Select an appropriate data (pivot) from the data sequence, and move data smaller than the pivot to the front and data larger than the pivot to the back. Sort each divided data A type of divide and conquer method Computational Time Worst-case time complexity O(n²) Best-case and average-case time complexity O(n log n) Implementation package main import ( "fmt" "math/rand" ) func quickSort ( n [] int ) [] int { if len ( n ) <= 1 { return n } pivot := n [ rand . Intn ( len ( n ))] low := make ([] int , 0 , len ( n )) high := make ([] int , 0 , len ( n )) middle := make ([] int , 0 , len ( n )) for _ , i := range n { switch { case i < pivot : low = append ( low , i ) case i == pivot : middle = append ( middle , i ) case i > pivot : high = append ( hig