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
Golang program for implementation LZW Data Compression and Uncompression
Golang program for implementation of Levenshtein distance
Golang program for implementation of Shell Sort
Golang program for implementation of Linked List
Golang program for implementation of Bubble Sort
Golang program for implementation of AVL Trees
Golang program for implementation of Radix Sort
Golang program to print all Permutations of a given string
Golang program for implementation of ZigZag Matrix
Golang program to generate number of slices permutations of number entered by user