한글 문서 | English Document

Go 언어로 작성된 다양한 정렬 알고리즘들이 있습니다

Go 언어가 설치 되어 있다면, go get 명령어를 실행하여 GoSoringAlgorithms 패키지를 받아옵니다.

$ go get github.com/kdgyun/GoSortingAlgorithms

간단합니다!

package main

import (
	"github.com/kdgyun/GoSortingAlgorithms/sorts"

	crand "crypto/rand"
	"fmt"
	"math"
	"math/big"
	"math/rand"
	"sort"
)

// 랜덤 정수 슬라이스 생성기
func SliceBuilder(len int) []int {
	seed, _ := crand.Int(crand.Reader, big.NewInt(math.MaxInt64))
	rand.Seed(seed.Int64())

	var slice []int
	for i := 0; i < len; i++ {
		slice = append(slice, rand.Int())
	}
	return slice
}

func main() {
	slice := SliceBuilder(1000000)
 
	sorts.QuickSort(slice) // sorts.____(slice []int)

	isSorted := sort.SliceIsSorted(slice, func(i, j int) bool {
		return slice[i] < slice[j]
	})
	fmt.Print(isSorted)
}

symplytest 를 통해 쉽게 테스트 할 수 있습니다.

package main

import (
	"github.com/kdgyun/GoSortingAlgorithms/simplytest"
)

func main() {
	simplytest.RunTest()
}

출력 예시

+==================================================================================+
|                                   Random Test                                    |
+==================================================================================+

...

[array length : 100000]
make arrays...
running bubble sort...
running cocktail sort...

...

running intro sort...
running parallel intro sort...
running cycle sort...

+-------------------------------------------------------------------------------------------------+
|                                name |                      ns |                 ms |     verify |      (err mag) 
|-------------------------------------------------------------------------------------------------|
|                         bubble sort |          13016202738 ns |           13016 ms |       true |
|-------------------------------------------------------------------------------------------------|
|                       cocktail sort |           8922656474 ns |            8922 ms |       true |
|-------------------------------------------------------------------------------------------------|
|                            tim sort |             11419013 ns |              11 ms |       true |
|-------------------------------------------------------------------------------------------------|
|                        bitonic sort |             32333072 ns |              32 ms |       true |
|-------------------------------------------------------------------------------------------------|

...

|-------------------------------------------------------------------------------------------------|
|                          intro sort |              6665792 ns |               6 ms |       true |
|-------------------------------------------------------------------------------------------------|
|                 parallel intro sort |              2537508 ns |               2 ms |       true |
|-------------------------------------------------------------------------------------------------|
|                          cycle sort |          20209957747 ns |           20209 ms |       true |
+-------------------------------------------------------------------------------------------------+

option.go를 통해 사용자가 쉽게 테스트 형식을 조정할 수 있으며, 3가지 주요 옵션을 제공합니다.

1. 정렬 알고리즘 선택 특정 정렬 알고리즘만 테스트 혹은 제외하고자 한다면 테스트하고자 하는 정렬 알고리즘 이름을 찾아 변수를 true 또는 false로 변경합니다. (True : 테스트 허용, false : 테스트 비허용)

   ex) SHELL_SORT Activate = true

2. 테스트 할 슬라이스의 길이 변경. 테스트할 슬라이스의 길이를 변경하려면 'lengths' 변수의 슬라이스를 원하는 값으로 설정 할 수 있습니다. 아래 예시는 길이 35, 50,000, 100,000 슬라이스에 대해 각각 테스트 하게 됩니다.

   ex) var lengths = [...]int{35, 50000, 100000}

3. 슬라이스 유형 변경.
   기본적으로 오름차순, 내림차순 및 랜덤 데이터로 구성된 각각의 모든 슬라이스가 테스트됩니다. 그러나 특정 데이터 유형을 비활성화하려면 변수를 false로 변경하면 됩니다.

   ex) ASCENDING_TEST Activate = false

Go 언어는 배열과 슬라이스가 구분되어 있습니다. 하지만, 일반적으로 기타 언어에서도 배열이 익숙하기 때문에 해당 알고리즘을 설명 할 때에는 배열로 통일하여 설명합니다.

현재 업데이트 된 정렬 알고리즘:

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
		or	Yes	Yes	total : , auxiliary :

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	Yes	total : , auxiliary :

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	Yes	total : , auxiliary :

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	No	total : , auxiliary :

*적용 된 Gap 시퀀스는 다음과 같습니다. Ciura sequence

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
or	depends on gap sequence	or	Yes	No	total : , auxiliary :

병합 정렬은 분할 정복 알고리즘을 기반으로 합니다.

개념적으로 병합 정렬은 다음과 같이 작동합니다:

1. 정렬되지 않은 n개의 요소를 갖는 배열을 재귀적으로 최소 하나 이상의 요소를 포함하는 배열이 되도록 절반으로 나눕니다(요소가 한 개만 있는 배열은 정렬된 것으로 간주됩니다).
2. 분할 된 배열이 모두 합쳐질 때 까지 반복적으로 병합하여 정렬 합니다.

3가지 유형의 병합 정렬을 지원합니다.

• top-down
  하향식 병합 정렬 알고리즘은 분할 된 배열의 크기가 1이 될 때까지 배열을 재귀적으로 분할한 다음 해당 하위 배열들을 병합하여 정렬된 목록을 생성합니다.
• bottom-up
  상향식 병합 정렬 알고리즘은 크기가 1인 n개의 하위 배열을 두 버퍼 사이에서 앞 뒤로 하위 배열들을 반복적으로 병합합니다.
• parallel
  병렬 병합 정렬 알고리즘은 재귀 호출의 병렬화를 통해 하위 배열의 크기가 임계값보다 작아질 때까지 배열을 재귀적으로 분할한 다음 병합하는 하향식 정렬을 수행합니다. 이 때, 임계값보다 작은 하위 배열들은 상향식 정렬을 사용하여 정렬하게 됩니다.

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			No	Yes	total : , auxiliary :

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	No	total : , auxiliary :

3가지 유형의 퀵 정렬을 지원합니다.

• left-pivot (+parallel)
  왼쪽 피벗 퀵 정렬은 왼쪽 요소를 피벗으로 선택하여 정렬합니다.
• middle-pivot (+parallel)
  중간 피벗 퀵 정렬은 중간 요소를 피벗으로 선택하여 정렬합니다.
• right-pivot (+parallel)
  오른쪽 피벗 퀵 정렬은 오른쪽 요소를 피벗으로 선택하여 정렬합니다.

또한 각 알고리즘은 재귀 호출의 병렬화도 지원합니다.

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	No	total : , auxiliary :

2가지 유형의 이중 피벗 퀵 정렬을 지원합니다.

• non-parallel
  정렬할 배열에서 두 개의 요소(피벗)를 선택하고 나머지 요소들을 작은 피벗(small pivot)보다 작은 요소, 피벗 사이에 있는 요소, 큰 피벗(big pivot)보다 큰 요소로 구분하여 배열을 분할하고 이러한 파티션을 재귀적인 과정을 통해 정렬하게 됩니다.
• parallel
  재귀 호출의 병렬화를 통해 각각의 정렬 알고리즘은 분할 된 배열의 크기가 임계값보다 작을 때까지 배열을 재귀적으로 분할한 배열을 병합하여 정렬하게 됩니다.

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	No	total : , auxiliary :

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	yes	total : , auxiliary :

Timsort는 다양한 종류의 실제 데이터에서 잘 수행되도록 설계된 알고리즘으로, 병합 정렬과 삽입 정렬(또는 이진 삽입 정렬)에서 파생되어 혼합 된 안정적인 하이브리드 정렬 알고리즘 입니다. Python 프로그래밍 언어에서 사용하기 위해 2002년 Tim Peters에 의해 구현되었습니다.

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	yes	total : , auxiliary :

2가지 유형의 알고리즘을 지원합니다.

• non-parallel
  분할 된 배열의 크기가 1이 될 때까지 배열을 재귀적으로 분할한 다음 Bitonic Sequencing Rule에 따라 해당 하위 배열을 병합하여 정렬하게 됩니다.
• parallel
  재귀 호출의 병렬화를 통해 분할 된 배열의 크기가 임계값보다 작아질 때까지 배열을 재귀적으로 분할한 다음 비병렬화로 전환하여 Bitonic Sequencing Rule에 따라 하위 배열을 분할 및 병합하여 생성합니다.

Type	Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
non-parallel				Yes	No	total : , auxiliary :
parallel				Yes	No	total : , auxiliary :

인트로 정렬은 최악의 경우에도 평균적으로 빠른 성능과 및 (점근적으로) 최적화 된 하이브리드 정렬 알고리즘입니다. 퀵정렬로 시작하여 재귀 깊이가 정렬되는 배열의 요소 개수에 따른 깊이 임계값(maximum depth: ) 수준을 초과하면 힙 정렬로 전환하고 분할 된 배열의 요소 개수가 길이 임계값(16) 미만이면 삽입 정렬로 전환합니다.

2가지 유형의 알고리즘을 지원합니다.

• non-parallel
  정렬할 배열에서 퀵 정렬을 사용할 때 요소(피벗)를 선택하고 선택 된 피벗을 제외한 다른 요소들이 피벗보다 작거나 큰지 여부에 따라 두 개의 하위 배열로 분할하고 재귀 깊이가 특정 임계값(maximum depth: )을 넘기 전까지 이러한 과정을 재귀적으로 거칩니다.

• parallel
  재귀 호출의 병렬화를 통해 각 병렬화 된 이중 피벗 퀵 정렬 알고리즘은 분할 된 배열의 크기가 임계값보다 작아지기 전까지 배열을 재귀적으로 분할하여 정렬합니다.

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	No	total : , auxiliary :

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	No	total : , auxiliary :

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	Yes	total : , auxiliary :

홀짝 병합 정렬은 사이즈는 , 깊이는 를 갖는 네트워크 정렬을 위해 Ken Batcher 정렬 알고리즘 입니다.

Type	Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
non-parallel				Yes	yes	total : , auxiliary :
parallel				Yes	yes	total : , auxiliary :

Worst-Case	Average-Case	Best-Case	in-place	stable	Space Complexity
			Yes	No	total : , auxiliary :