Golang Data Structure - Median of Medians

Median of Medians (중앙값의 중앙값)

컴퓨터 과학에서 중앙값의 중앙값은 대략적인 (중앙값) 선택 알고리즘으로, k 번째로 작은 요소를 선택하는 정확한 선택 알고리즘, 주로 빠른 선택을위한 좋은 피벗을 제공하는 데 자주 사용됩니다. 다음은 K 번째 가장 작은 요소를 찾기 위해 Medians의 Median으로 이동 프로그램의 소스 코드입니다.

컴퓨터 과학에서 Median of Medians는 대략적인 중앙값 선택 알고리즘으로, 초기에 정렬되지 않은 배열에서 k번째로 작은 원소를 선택하는 가장 일반적인 알고리즘인 Quickselect에 대한 좋은 피봇을 제공하는 데 자주 사용됩니다. Median of Medians는 선형 시간에 대략적인 중앙값을 찾아냅니다. 이 중앙값을 개선된 피봇으로 사용하면, Quickselect의 최악의 경우 복잡도는 이차적인 것에서 선형적으로 감소하게 되며, 이는 모든 선택 알고리즘의 최악의 경우 복잡도에 대해 점근적으로 최적의 것입니다. 다시 말해, Median of Medians는 좋은 피벗 원소를 생성하여 점근적으로 최적의 정확한 일반 선택 알고리즘을 구축하는 데 도움이 되는 대략적인 중앙값 선택 알고리즘입니다(특히 최악의 경우 복잡도에 대한 의미에서).

영문위키:
https://en.wikipedia.org/wiki/Median_of_medians

Median of medians - Wikipedia

코드 설명 :

 

아래의 코드는 "Median of Medians" 알고리즘을 구현한 예시 코드입니다. 이 알고리즘은 임의의 길이의 숫자 배열에서 k번째로 작은 값을 찾는 데 사용됩니다. 이 알고리즘은 분할정복을 사용하며, 배열을 일정한 크기의 하위 배열로 나누어 중간값(median)을 찾고, 중간값을 피봇(pivot)으로 사용하여 배열을 둘로 분할합니다. 그런 다음 k번째로 작은 값을 찾을 때, 왼쪽 부분 배열에 k-1개 이하의 요소가 있다면 왼쪽 부분 배열에서 재귀적으로 찾고, 오른쪽 부분 배열에 k-1개 이상의 요소가 있다면 오른쪽 부분 배열에서 재귀적으로 찾습니다.

아래의 코드에서는 medianOfMedians 함수가 Median of Medians 알고리즘을 구현하고, main 함수에서 이 함수를 호출하여 숫자 배열에서 k번째로 작은 값을 찾습니다. sort 패키지를 사용하여 입력 배열을 정렬한 후, medianOfMedians 함수에서 Median of Medians 알고리즘을 사용하여 k번째로 작은 값을 찾습니다. 이 함수는 재귀적으로 호출되며, 배열의 길이가 10보다 작아질 때까지 하위 배열을 만듭니다. 최종적으로 k번째로 작은 값을 반환합니다.

 

함수 및 주요 변수 설명:

 

func medianOfMedians(sliceList []int, k, r int) int :
정수 조각(sliceList), 정수 값(k) 및 다른 정수 값(r)을 입력으로 사용하고 정수 값을 출력으로 반환하는 재귀 함수를 정의합니다
arr = make([]int, len(sliceList[(i*r):])):  현재 하한에서 끝까지 입력 슬라이스의 요소 수와 동일한 길이로 현재 중위수에 대한 새 슬라이스를 초기화합니다. 
copy(arr, sliceList[(i*r):]): 현재 중위수에 대한 입력 슬라이스의 요소를 새 슬라이스로 복사합니다.
copy(arr, sliceList[(i*r):v]):  현재 하한 및 상한 내에서 현재 중위수에 대한 입력 슬라이스의 요소를 새 슬라이스로 복사합니다. 

pivot := medianOfMedians(medians, (len(medians)+1)/2, r): 입력 슬라이스를 분할하기 위한 피벗 값으로 중위수를 계산합니다.

 

 

Go 소스코드

package main

import (
	"fmt"
	"sort"
)

// Go에서 배열과 슬라이스는  다릅니다.

// 배열: 고정 크기의 메모리 블록입니다. 정적으로 할당되며 크기는 초기화할 때 결정됩니다. 배열의 크기를 바꿀 수 없습니다.
// 슬라이스: 배열의 일부를 참조하는 동적 크기의 구조입니다. 슬라이스는 make() 함수로 생성되거나 슬라이스 리터럴로 생성됩니다. 슬라이스는 길이와 용량이 있으며 용량은 내부 배열의 길이입니다. 슬라이스의 크기는 필요에 따라 동적으로 늘어날 수 있습니다.
// 따라서 슬라이스는 동적으로 크기를 조정할 수 있으므로 좀 더 유연하고 배열은 고정 크기를 가지므로 메모리 사용량이 더 효율적입니다. 또한 배열은 값 타입이고 슬라이스는 참조 타입입니다.

func medianOfMedians(sliceList []int, k, r int) int {

	//배열 크기 지정
	num := len(sliceList)
	//num이 10 미만일 때 조건문 실행
	if num < 10 {
		//Int형으로 정렬함
		sort.Ints(sliceList)
		//10미만이면 sliceList[k-1]을 리턴
		return sliceList[k-1]
	}

	//med 값 설정
	med := (num + r - 1) / r
	fmt.Println("med1", med)

	//슬라이스 생성
	medians := make([]int, med)
	fmt.Println("med2", med)
	fmt.Println("medians", medians)

	for i := 0; i < med; i++ {

		v := (i * r) + r

		var arr []int

		if v >= num {
			//슬라이스 생성
			arr = make([]int, len(sliceList[(i*r):]))
			//arr 변수로 sliceList[(i*r)]을 복사한다.
			copy(arr, sliceList[(i*r):])
		} else {
			//슬라이스 생성
			arr = make([]int, r)
			//arr 변수로 sliceList[(i*r):v]을 복사한다.
			copy(arr, sliceList[(i*r):v])
		}
		//Int형으로 오름차순 정렬
		sort.Ints(arr)
		//arr길이의 1/2 인덱스의 원소를 medians[i]로 지정
		medians[i] = arr[len(arr)/2]
	}

	pivot := medianOfMedians(medians, (len(medians)+1)/2, r)
	fmt.Println("pivot", pivot)
	var leftSide, rightSide []int

	for i := range sliceList {
		if sliceList[i] < pivot {
			// append 함수는 슬라이스에 값을 추가할 때 사용하는 함수입니다.
			// leftSide 변수는 빈 슬라이스로 선언되었기 때문에 append 함수를 사용하여 sliceList[i] 값을 추가하면 leftSide 슬라이스에 그 값이 저장됩니다.
			leftSide = append(leftSide, sliceList[i])
		} else if sliceList[i] > pivot {
			rightSide = append(rightSide, sliceList[i])
		}
	}
	fmt.Println("leftSide", leftSide)
	fmt.Println("rightSide", rightSide)

	switch {

	//k == len(leftSide) + 1 길이와 같을 때
	case k == (len(leftSide) + 1):
		return pivot

		//k == len(leftSide)길이 이하일 대
	case k <= len(leftSide):
		return medianOfMedians(leftSide, k, r)
		//디폴트로 설정
	default:
		return medianOfMedians(rightSide, k-len(leftSide)-1, r)
	}
}

// main 함수에서는 medianOfMedians 함수를 사용하여 정수 슬라이스에서 k번째로 작은 요소를 찾습니다.
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}
	fmt.Println("intSlice 1", intSlice)
	sort.Ints(intSlice)
	fmt.Println("intSlice 2", intSlice)

	for _, j := range []int{5, 10, 15, 20} {

		i := medianOfMedians(intSlice, j, 5)
		//j번째 엘리먼트는 i
		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")
		}

	}
}

 

 

go Println 입출력값

go run MedianOfMedians.go 
intSlice 1 [5 9 77 62 71 11 22 46 36 18 19 33 75 17 39 41 73 50 217 79 120]
intSlice 2 [5 9 11 17 18 19 22 33 36 39 41 46 50 62 71 73 75 77 79 120 217]
med1 5
med2 5
medians [0 0 0 0 0]
pivot 50
leftSide [5 9 11 17 18 19 22 33 36 39 41 46]
rightSide [62 71 73 75 77 79 120 217]
med1 3
med2 3
medians [0 0 0]
pivot 33
leftSide [5 9 11 17 18 19 22]
rightSide [36 39 41 46]
5 smallest element =  18
arr[ 4 ]= 18
med1 5
med2 5
medians [0 0 0 0 0]
pivot 50
leftSide [5 9 11 17 18 19 22 33 36 39 41 46]
rightSide [62 71 73 75 77 79 120 217]
med1 3
med2 3
medians [0 0 0]
pivot 33
leftSide [5 9 11 17 18 19 22]
rightSide [36 39 41 46]
10 smallest element =  39
arr[ 9 ]= 39
med1 5
med2 5
medians [0 0 0 0 0]
pivot 50
leftSide [5 9 11 17 18 19 22 33 36 39 41 46]
rightSide [62 71 73 75 77 79 120 217]
15 smallest element =  71
arr[ 14 ]= 71
med1 5
med2 5
medians [0 0 0 0 0]
pivot 50
leftSide [5 9 11 17 18 19 22 33 36 39 41 46]
rightSide [62 71 73 75 77 79 120 217]
20 smallest element =  120
arr[ 19 ]= 120