GoSortingAlgorithms

README

한글 문서 | English Document

GoSortingAlgorithms

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

🔰 설치 방법

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

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

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

name	function name
Bubble Sort	BubbleSort
Cocktail Sort	CocktailSort
Insertion Sort	InsertionSort
Selection Sort	SelectionSort
Shell Sort	ShellSort
Merge Sort (bottom-up)	BottomUpMergeSort
Merge Sort (top-down)	TopDownMergeSort
Merge Sort (parallel)	ParallelMergeSort
Heap Sort	HeapSort
Quick Sort (left-pivot)	QuickSortLP
Quick Sort (middle-pivot)	QuickSort
Quick Sort (left-pivot)	QuickSortRP
Quick Sort (left-pivot with parallel)	ParallelQuickSortLP
Quick Sort (middle-pivot with parallel)	ParallelQuickSort
Quick Sort (left-pivot with parallel)	ParallelQuickSortRP
Dual-pivot Quick Sort	DualPivotQuickSort
Dual-pivot Quick Sort (parallel)	ParallelDualPivotQuickSort
Binaray Insertion Sort	BinarySort
Tim Sort	TimSort
Bitonic Sort	BitonicSort
Bitonic Sort (parallel)	ParallelBitonicSort
Intro Sort	IntroSort
Intro Sort (parallel)	ParallelIntroSort
Cycle Sort	CycleSort
Odd-Even Sort	OddEvenSort
Odd-Even Merge Sort	OddEvenMergeSort
Odd-Even Merge Sort (parallel)	ParallelOddEvenMergeSort
Comb Sort	CombSort

Bubble Sort

버블 정렬은 인접한 요소를 반복적으로 비교하고 교환하는 방식입니다. 해당 구현은 이미 배열이 정렬되어있는 경우 정렬을 종료하도록 최적화되어 있습니다. 최적화를 원하지 않는다면, bubbleSort 함수에서 swapped 변수를 삭제 및 해당 조건문을 삭제하면 됩니다.

COMPLEXITY

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

Cocktail Sort

칵테일 정렬은 버블 정렬을 기반한 변형 된 알고리즘입니다. Cocktail shaker sort(칵테일 셰이커 정렬), bidirectional bubble sort(양방향 버블 정렬), cocktail sort(칵테일 정렬), shaker sort(셰이커 정렬) 이라고도 불립니다.

COMPLEXITY

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

Insertion Sort

삽입 정렬은 각 반복마다 배열의 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입요소를 찾아 올바른 위치에 배치하게 됩니다.

COMPLEXITY

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

Selection Sort

선택 정렬은 정렬되지 않은 부분에서 각 반복을 통해 가장 작은 요소를 찾아 앞 위치에 배치하게 됩니다.

COMPLEXITY

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

Shell Sort

셸 정렬은 삽입 정렬을 확장한 버전입니다. 먼저 일정 간격으로 서로 멀리 떨어져 있는 요소를 삽입 정렬해 나가면서 다음에는 그 사이의 간격을 줄여나가면서 정렬하게 됩니다.

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

COMPLEXITY

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

Merge Sort

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

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

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

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

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

COMPLEXITY

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

Heap Sort

힙 정렬은 배열을 힙의 원리처럼 배열에서 요소를 하나씩 제거한 다음 배열의 정렬된 부분에 삽입하여 정렬하게 됩니다.

COMPLEXITY

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

Quick Sort

퀵 정렬은 배열에서 특정 피벗을 선택한 다음 피벗보다 작은지 큰지에 따라 다른 요소를 두 개의 하위 배열로 분할하게 되는 분할 정복 알고리즘을 기반으로 합니다. 재귀적으로 이 과정을 거쳐 정렬됩니다.

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

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

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

COMPLEXITY

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

Dual-Pivot Quick Sort

이중 피벗 퀵 정렬은 Quick Sort를 기반으로 하지만, 배열에서 두 개의 요소를 피벗(pivot)으로 선택하여 정렬하는 방식에 차이가 있습니다. 정렬할 배열에서 두 개의 요소(피벗)를 선택하고 나머지 요소들을 작은 피벗(small pivot)보다 작은 요소, 피벗 사이에 있는 요소, 큰 피벗(big pivot)보다 큰 요소로 구분하여 배열을 분할하고 이러한 파티션을 재귀적인 과정을 통해 정렬하게 됩니다.

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

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

COMPLEXITY

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

Binary Insertion Sort

이진 삽입 정렬은 삽입 정렬을 기반으로 한 확장 버전입니다. 이진 정렬이라고도 합니다. 이진 삽입 정렬은 이진 검색(Binary Search)을 사용하여 각 반복 과정에서 특정 요소를 삽입할 위치를 찾아 삽입하게 됩니다.

COMPLEXITY

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

Tim Sort

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

COMPLEXITY

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

Bitonic Sort

바이토닉 정렬은 병렬로 실행할 수 있는 비교 기반 정렬 알고리즘입니다. 무작위 숫자 시퀀스를 단조 증가했다가 감소하는 비트 시퀀스로 변환하는 데 중점을 둡니다. 병렬 환경에 최적화 되어있으며 GPU 병렬 처리로 사용되기도 하지만, 여기서는 기타 병렬화한 정렬 알고리즘들과 마찬가지로 GO 언어의 동시성 모델로 구현됩니다.

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

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

COMPLEXITY

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

Intro Sort

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

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

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

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

COMPLEXITY

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

Cycle Sort

순환 정렬은 in-place 정렬이자 불안정 정렬 알고리즘으로, 배열에 대해 총 쓰기(write) 수의 관점에서 가장 적게 쓰기 위한 비교 정렬 알고리즘 입니다.

COMPLEXITY

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

Odd-Even Sort

컴퓨팅 시스템 관점에서 홀짝 정렬은 원래 상호 로컬 연결의 병렬 프로세서에서 사용하기 위해 개발된 비교적 간단한 정렬 알고리즘입니다

COMPLEXITY

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

Odd-Even Merge Sort

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

COMPLEXITY

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

Comb Sort

콤 정렬은 원래 1980년 Włodzimierz Dobosiewicz와 Artur Borowy가 설계한 비교적 간단한 정렬 알고리즘으로, 나중에 Stephen Lacey와 Richard Box가 1991년에 재발견(이 때 "Combsort"라고 이름을 지정)했습니다. Comb 정렬은 셸 정렬과 유사한 방식으로 버블 정렬을 개선하여 성능을 향상 시킨 정렬 알고리즘입니다.

COMPLEXITY

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