Dark Mode

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

kdgyun/GoSortingAlgorithms

Repository files navigation

hangeul munseo | English Document


GoSortingAlgorithms


Go eoneoro jagseongdoen dayanghan jeongryeol algorijeumdeuli issseubnida



seolci bangbeob

Go eoneoga seolci doeeo issdamyeon, go get myeongryeongeoreul silhaenghayeo GoSoringAlgorithms paekijireul badaobnida.

$ go get github.com/kdgyun/GoSortingAlgorithms



sayong seolmyeongseo

gandanhabnida!

package main

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

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

// raendeom jeongsu seulraiseu saengseonggi
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)
}



gandanhan teseuteu bangbeob

symplytest reul tonghae swibge teseuteu hal su issseubnida.

package main

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

func main() {
simplytest.RunTest()
}


culryeog yesi


+==================================================================================+
| 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.goreul tonghae sayongjaga swibge teseuteu hyeongsigeul jojeonghal su isseumyeo, 3gaji juyo obsyeoneul jegonghabnida.

  1. jeongryeol algorijeum seontaeg teugjeong jeongryeol algorijeumman teseuteu hogeun jeoehagoja handamyeon teseuteuhagoja haneun jeongryeol algorijeum ireumeul caja byeonsureul true ddoneun falsero byeongyeonghabnida. (True : teseuteu heoyong, false : teseuteu biheoyong)

    ex) SHELL_SORT Activate = true

  2. teseuteu hal seulraiseuyi gili byeongyeong. teseuteuhal seulraiseuyi gilireul byeongyeongharyeomyeon 'lengths' byeonsuyi seulraiseureul weonhaneun gabseuro seoljeong hal su issseubnida. arae yesineun gili 35, 50,000, 100,000 seulraiseue daehae gaggag teseuteu hage doebnida.

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

  3. seulraiseu yuhyeong byeongyeong.
    gibonjeogeuro oreumcasun, naerimcasun mic raendeom deiteoro guseongdoen gaggagyi modeun seulraiseuga teseuteudoebnida. geureona teugjeong deiteo yuhyeongeul bihwalseonghwaharyeomyeon byeonsureul falsero byeongyeonghamyeon doebnida.

    ex) ASCENDING_TEST Activate = false



gaeyo

Go eoneoneun baeyeolgwa seulraiseuga gubundoeeo issseubnida. hajiman, ilbanjeogeuro gita eoneoeseodo baeyeoli igsughagi ddaemune haedang algorijeumeul seolmyeong hal ddaeeneun baeyeolro tongilhayeo seolmyeonghabnida.

hyeonjae eobdeiteu doen jeongryeol algorijeum:

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


beobeul jeongryeoleun injeobhan yosoreul banbogjeogeuro bigyohago gyohwanhaneun bangsigibnida. haedang guhyeoneun imi baeyeoli jeongryeoldoeeoissneun gyeongu jeongryeoleul jongryohadorog coejeoghwadoeeo issseubnida. coejeoghwareul weonhaji anhneundamyeon, bubbleSort hamsueseo swapped byeonsureul sagje mic haedang jogeonmuneul sagjehamyeon doebnida.

COMPLEXITY

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


Cocktail Sort


kagteil jeongryeoleun beobeul jeongryeoleul gibanhan byeonhyeong doen algorijeumibnida. Cocktail shaker sort(kagteil syeikeo jeongryeol), bidirectional bubble sort(yangbanghyang beobeul jeongryeol), cocktail sort(kagteil jeongryeol), shaker sort(syeikeo jeongryeol) iragodo bulribnida.

COMPLEXITY

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


Insertion Sort


sabib jeongryeoleun gag banbogmada baeyeolyi apeseobuteo caryedaero imi jeongryeoldoen baeyeol bubungwa bigyohayeo jasinyi wicireul caja sabibyosoreul caja olbareun wicie baecihage doebnida.

COMPLEXITY

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


Selection Sort


seontaeg jeongryeoleun jeongryeoldoeji anheun bubuneseo gag banbogeul tonghae gajang jageun yosoreul caja ap wicie baecihage doebnida.

COMPLEXITY

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


Shell Sort


syel jeongryeoleun sabib jeongryeoleul hwagjanghan beojeonibnida. meonjeo iljeong gangyeogeuro seoro meolri ddeoleojyeo issneun yosoreul sabib jeongryeolhae nagamyeonseo daeumeneun geu saiyi gangyeogeul julyeonagamyeonseo jeongryeolhage doebnida.

*jeogyong doen Gap sikweonseuneun daeumgwa gatseubnida. 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


byeonghab jeongryeoleun bunhal jeongbog algorijeumeul gibaneuro habnida.

gaenyeomjeogeuro byeonghab jeongryeoleun daeumgwa gati jagdonghabnida:

  1. jeongryeoldoeji anheun ngaeyi yosoreul gajneun baeyeoleul jaegwijeogeuro coeso hana isangyi yosoreul pohamhaneun baeyeoli doedorog jeolbaneuro nanubnida(yosoga han gaeman issneun baeyeoleun jeongryeoldoen geoseuro ganjudoebnida).
  2. bunhal doen baeyeoli modu habcyeojil ddae ggaji banbogjeogeuro byeonghabhayeo jeongryeol habnida.


3gaji yuhyeongyi byeonghab jeongryeoleul jiweonhabnida.

  • top-down
    hahyangsig byeonghab jeongryeol algorijeumeun bunhal doen baeyeolyi keugiga 1i doel ddaeggaji baeyeoleul jaegwijeogeuro bunhalhan daeum haedang hawi baeyeoldeuleul byeonghabhayeo jeongryeoldoen mogrogeul saengseonghabnida.
  • bottom-up
    sanghyangsig byeonghab jeongryeol algorijeumeun keugiga 1in ngaeyi hawi baeyeoleul du beopeo saieseo ap dwiro hawi baeyeoldeuleul banbogjeogeuro byeonghabhabnida.
  • parallel
    byeongryeol byeonghab jeongryeol algorijeumeun jaegwi hoculyi byeongryeolhwareul tonghae hawi baeyeolyi keugiga imgyegabsboda jagajil ddaeggaji baeyeoleul jaegwijeogeuro bunhalhan daeum byeonghabhaneun hahyangsig jeongryeoleul suhaenghabnida. i ddae, imgyegabsboda jageun hawi baeyeoldeuleun sanghyangsig jeongryeoleul sayonghayeo jeongryeolhage doebnida.

COMPLEXITY

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


Heap Sort


hib jeongryeoleun baeyeoleul hibyi weonriceoreom baeyeoleseo yosoreul hanassig jegeohan daeum baeyeolyi jeongryeoldoen bubune sabibhayeo jeongryeolhage doebnida.

COMPLEXITY

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


Quick Sort


kwig jeongryeoleun baeyeoleseo teugjeong pibeoseul seontaeghan daeum pibeosboda jageunji keunjie ddara dareun yosoreul du gaeyi hawi baeyeolro bunhalhage doeneun bunhal jeongbog algorijeumeul gibaneuro habnida. jaegwijeogeuro i gwajeongeul geocyeo jeongryeoldoebnida.

3gaji yuhyeongyi kwig jeongryeoleul jiweonhabnida.

  • left-pivot (+parallel)
    oenjjog pibeos kwig jeongryeoleun oenjjog yosoreul pibeoseuro seontaeghayeo jeongryeolhabnida.
  • middle-pivot (+parallel)
    junggan pibeos kwig jeongryeoleun junggan yosoreul pibeoseuro seontaeghayeo jeongryeolhabnida.
  • right-pivot (+parallel)
    oreunjjog pibeos kwig jeongryeoleun oreunjjog yosoreul pibeoseuro seontaeghayeo jeongryeolhabnida.

ddohan gag algorijeumeun jaegwi hoculyi byeongryeolhwado jiweonhabnida.

COMPLEXITY

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


Dual-Pivot Quick Sort


ijung pibeos kwig jeongryeoleun Quick Sortreul gibaneuro hajiman, baeyeoleseo du gaeyi yosoreul pibeos(pivot)euro seontaeghayeo jeongryeolhaneun bangsige caiga issseubnida. jeongryeolhal baeyeoleseo du gaeyi yoso(pibeos)reul seontaeghago nameoji yosodeuleul jageun pibeos(small pivot)boda jageun yoso, pibeos saie issneun yoso, keun pibeos(big pivot)boda keun yosoro gubunhayeo baeyeoleul bunhalhago ireohan patisyeoneul jaegwijeogin gwajeongeul tonghae jeongryeolhage doebnida.

2gaji yuhyeongyi ijung pibeos kwig jeongryeoleul jiweonhabnida.

  • non-parallel
    jeongryeolhal baeyeoleseo du gaeyi yoso(pibeos)reul seontaeghago nameoji yosodeuleul jageun pibeos(small pivot)boda jageun yoso, pibeos saie issneun yoso, keun pibeos(big pivot)boda keun yosoro gubunhayeo baeyeoleul bunhalhago ireohan patisyeoneul jaegwijeogin gwajeongeul tonghae jeongryeolhage doebnida.
  • parallel
    jaegwi hoculyi byeongryeolhwareul tonghae gaggagyi jeongryeol algorijeumeun bunhal doen baeyeolyi keugiga imgyegabsboda jageul ddaeggaji baeyeoleul jaegwijeogeuro bunhalhan baeyeoleul byeonghabhayeo jeongryeolhage doebnida.

COMPLEXITY

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


Binary Insertion Sort


ijin sabib jeongryeoleun sabib jeongryeoleul gibaneuro han hwagjang beojeonibnida. ijin jeongryeoliragodo habnida. ijin sabib jeongryeoleun ijin geomsaeg(Binary Search)eul sayonghayeo gag banbog gwajeongeseo teugjeong yosoreul sabibhal wicireul caja sabibhage doebnida.

COMPLEXITY

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


Tim Sort


Timsortneun dayanghan jongryuyi silje deiteoeseo jal suhaengdoedorog seolgyedoen algorijeumeuro, byeonghab jeongryeolgwa sabib jeongryeol(ddoneun ijin sabib jeongryeol)eseo pasaengdoeeo honhab doen anjeongjeogin haibeurideu jeongryeol algorijeum ibnida. Python peurogeuraeming eoneoeseo sayonghagi wihae 2002nyeon Tim Peterse yihae guhyeondoeeossseubnida.

COMPLEXITY

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


Bitonic Sort


baitonig jeongryeoleun byeongryeolro silhaenghal su issneun bigyo giban jeongryeol algorijeumibnida. mujagwi susja sikweonseureul danjo jeunggahaessdaga gamsohaneun biteu sikweonseuro byeonhwanhaneun de jungjeomeul dubnida. byeongryeol hwangyeonge coejeoghwa doeeoisseumyeo GPU byeongryeol ceoriro sayongdoegido hajiman, yeogiseoneun gita byeongryeolhwahan jeongryeol algorijeumdeulgwa macangajiro GO eoneoyi dongsiseong modelro guhyeondoebnida.

2gaji yuhyeongyi algorijeumeul jiweonhabnida.

  • non-parallel
    bunhal doen baeyeolyi keugiga 1i doel ddaeggaji baeyeoleul jaegwijeogeuro bunhalhan daeum Bitonic Sequencing Rulee ddara haedang hawi baeyeoleul byeonghabhayeo jeongryeolhage doebnida.
  • parallel
    jaegwi hoculyi byeongryeolhwareul tonghae bunhal doen baeyeolyi keugiga imgyegabsboda jagajil ddaeggaji baeyeoleul jaegwijeogeuro bunhalhan daeum bibyeongryeolhwaro jeonhwanhayeo Bitonic Sequencing Rulee ddara hawi baeyeoleul bunhal mic byeonghabhayeo saengseonghabnida.

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


inteuro jeongryeoleun coeagyi gyeonguedo pyeonggyunjeogeuro bbareun seongneunggwa mic (jeomgeunjeogeuro) coejeoghwa doen haibeurideu jeongryeol algorijeumibnida. kwigjeongryeolro sijaghayeo jaegwi gipiga jeongryeoldoeneun baeyeolyi yoso gaesue ddareun gipi imgyegabs(maximum depth: ) sujuneul cogwahamyeon hib jeongryeolro jeonhwanhago bunhal doen baeyeolyi yoso gaesuga gili imgyegabs(16) mimanimyeon sabib jeongryeolro jeonhwanhabnida.



2gaji yuhyeongyi algorijeumeul jiweonhabnida.

  • non-parallel
    jeongryeolhal baeyeoleseo kwig jeongryeoleul sayonghal ddae yoso(pibeos)reul seontaeghago seontaeg doen pibeoseul jeoehan dareun yosodeuli pibeosboda jaggeona keunji yeobue ddara du gaeyi hawi baeyeolro bunhalhago jaegwi gipiga teugjeong imgyegabs(maximum depth: )eul neomgi jeonggaji ireohan gwajeongeul jaegwijeogeuro geocibnida.

  • parallel
    jaegwi hoculyi byeongryeolhwareul tonghae gag byeongryeolhwa doen ijung pibeos kwig jeongryeol algorijeumeun bunhal doen baeyeolyi keugiga imgyegabsboda jagajigi jeonggaji baeyeoleul jaegwijeogeuro bunhalhayeo jeongryeolhabnida.


COMPLEXITY

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


Cycle Sort


sunhwan jeongryeoleun in-place jeongryeolija bulanjeong jeongryeol algorijeumeuro, baeyeole daehae cong sseugi(write) suyi gwanjeomeseo gajang jeogge sseugi wihan bigyo jeongryeol algorijeum ibnida.

COMPLEXITY

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


Odd-Even Sort


keompyuting siseutem gwanjeomeseo holjjag jeongryeoleun weonrae sangho rokeol yeongyeolyi byeongryeol peuroseseoeseo sayonghagi wihae gaebaldoen bigyojeog gandanhan jeongryeol algorijeumibnida

COMPLEXITY

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


Odd-Even Merge Sort


holjjag byeonghab jeongryeoleun saijeuneun , gipineun reul gajneun neteuweokeu jeongryeoleul wihae Ken Batcher jeongryeol algorijeum ibnida.


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


kom jeongryeoleun weonrae 1980nyeon Wlodzimierz Dobosiewiczwa Artur Borowyga seolgyehan bigyojeog gandanhan jeongryeol algorijeumeuro, najunge Stephen Laceywa Richard Boxga 1991nyeone jaebalgyeon(i ddae "Combsort"rago ireumeul jijeong)haessseubnida. Comb jeongryeoleun syel jeongryeolgwa yusahan bangsigeuro beobeul jeongryeoleul gaeseonhayeo seongneungeul hyangsang sikin jeongryeol algorijeumibnida.

COMPLEXITY

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