Golang program for implementation of Median of Medians
In computer science, the median of medians is an approximate (median) selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, mainly the quick-select, that selects kth smallest element. Here is source code of the Go Program to Median of Medians to find the Kth Smallest element.
Example
package main
import (
"fmt"
"sort"
)
func medianOfMedians(sliceList []int, k, r int) int {
num := len(sliceList)
if num < 10 {
sort.Ints(sliceList)
return sliceList[k-1]
}
med := (num + r - 1) / r
medians := make([]int, med)
for i := 0; i < med; i++ {
v := (i * r) + r
var arr []int
if v >= num {
arr = make([]int, len(sliceList[(i*r):]))
copy(arr, sliceList[(i*r):])
} else {
arr = make([]int, r)
copy(arr, sliceList[(i*r):v])
}
sort.Ints(arr)
medians[i] = arr[len(arr)/2]
}
pivot := medianOfMedians(medians, (len(medians)+1)/2, r)
var leftSide, rightSide []int
for i := range sliceList {
if sliceList[i] < pivot {
leftSide = append(leftSide, sliceList[i])
} else if sliceList[i] > pivot {
rightSide = append(rightSide, sliceList[i])
}
}
switch {
case k == (len(leftSide) + 1):
return pivot
case k <= len(leftSide):
return medianOfMedians(leftSide, k, r)
default:
return medianOfMedians(rightSide, k-len(leftSide)-1, r)
}
}
func main() {
intSlice := []int{5, 9, 77, 62, 71, 11, 22, 46, 36, 18, 19, 33, 75, 17, 39, 41, 73, 50, 217, 79, 120}
sort.Ints(intSlice)
for _, j := range []int{5, 10, 15, 20} {
i := medianOfMedians(intSlice, j, 5)
fmt.Println(j, "smallest element = ", i)
v := intSlice[j-1]
fmt.Println("arr[", j-1, "] = ", v)
if i != v {
fmt.Println("Oops! Algorithm is wrong")
}
}
}
Output
5 smallest element = 18
arr[ 4 ] = 18
10 smallest element = 39
arr[ 9 ] = 39
15 smallest element = 71
arr[ 14 ] = 71
20 smallest element = 120
arr[ 19 ] = 120
Most Helpful This Week
How to create Slice using Make function in Golang?
GO Program to Find the Largest Number Among Three Numbers
Example to use various String Functions in Go Language
Struct Instantiation Using Pointer Address Operator
Golang program for implementation of Huffman Coding Algorithm
Golang program for implementation LZW Data Compression and Uncompression