정렬 알고리즘들

출처는 위키피디아와 구글
https://en.m.wikipedia.org/wiki/Sorting_algorithm#Shellsort

1945 by 노이만
병합정렬(Merge Sort)

->가장 안정적인 정렬 알고리즘 중 하나.
->O(n log2 n)의 복잡도를 가진다.
->따로 저장공간을 쓰기 때문에 메모리의 문제가 좀 있긴 하다. 구현하기에 따라 추가공간을 쓰지 않을 수도 있다.
->웬만한 stable_sort는 병합정렬이나 병합정렬의 변종으로 구현된다.

1951 by Betty Holberton
버블정렬

가장 느려터진 정렬중 하나.
->O(N^2)의 복잡도

??? by ???
선택정렬(Selection Sort)
->O(N^2)의 복잡도
->매번 값을 옮기는건 아니라 버블보단 빠르다.

1946 by John Mauchly
삽입정렬(Insertion Sort)
->O(N^2)의 복잡도.
->굉장히 느리지만, 정렬이 거의 다 된 상황에서는 빠르다는 이점이 있어서 다른 알고리즘과 섞여쓰이기도 한다.

??? by ???
칵테일 정렬(Cocktail Shaker Sort)

->버블정렬의 변종이다.
->양방향 버블정렬, 칵테일셰이커라고도 불린다.
->당연히 느리다. O(N).
->쓸데는 없다.

1954 by Harold H. Seward
계수정렬(Counting Sort)
->정수에만 사용 가능. 정수의 최대 범위를 알수 있을 경우에만 사용 가능
->O(N)의 복잡도 보장.
->정수의 범위에 따라 속도가 달라진다.

1959 by Donald Shell
셸 정렬(Shell Sort)

->복잡도가 애매함
->특정 간격을 설정하고, 간격 그룹별로 쪼개서 정렬하고 합치면서 정렬을 완성하는    알고리즘이다.
->특별히 빠른건 아니라서.. 쓸일은 없다.

1959 by Tony Hoare
퀵정렬(Quick Sort)

->피벗을 놓고 분할해서 정렬하는 방식이다.
->평균 O(N log N), 최악 O(N^2)
->대체로 매우 빠른 편이지만 안정성이 떨어진다.
->그래도 평균성능은 거의 압도적이라, 상당수의 정렬이 이 알고리즘을 기반으로 구현된다.

1964 by J. W. J. Williams
힙정렬(Heap Sort)

->자료구조인 힙에 넣었다 빼면서 정렬하는 방식이다.
->복잡도는 O(N log N)
->특별히 빠르진 않지만 안정적인 편이다.

1991 by Włodzimierz Dobosiewicz, Stephen Lacey, Richard Box(고안은 1980)
빗질 정렬(Comb Sort)

->버블정렬의 변종
->뭐 어떻게 버블의 문제점을 개선했다고 하는데, 모르겠다.
->아무튼 버블보다 빠르긴 한데. 애매하다. 쓸일은 없을것같다.

1997 by David Musser
인트로 정렬(Intro Sort)

->퀵정렬과 힙정렬, 삽입정렬이 섞인 하이브리드소트다.
->C++의 std::sort가 이 알고리즘을 사용한다.

2000 by Hamid Sarbazi-Azad
놈 정렬(Gnome Sort)

->삽입소트와 버블소트의 특징이 섞였다는 것 같다.
->그래도 결국 O(N^2)으로 느리다. 쓸일은 없겠다.

2002 by by Joshua J. Arulanandham, Cristian S. Calude, Michael J. Dinneen
Bead Sort
->Gravity Sort라고도 한다.
->자연수에만 쓸수 있다고 한다.
->공간적 낭비가 심하다. 최악 O(N^2)의 공간을 사용한다.
->그대신 시간복잡도는 최악이 O(N)이다. O(root N), O(1)도 기대할 수 있다.

2002 by  Tim Peters
팀 정렬(Tim Sort)

->병합정렬과 삽입정렬이 섞인 하이브리드 소트다.
->O(N log N)으로 빠르면서 안정적이다.
->팀이라는 양반이 파이썬으로 구현했다고 한다.
->자바와 파이썬에서 주로 쓰이는것 같다.

2002 by Steven J. Ross
스프레드 정렬(Spread Sort)
->기수정렬, 버킷정렬, 퀵정렬, 병합정렬이 섞인 혼종.
->최악 복잡도 : O(n log n)
->최악만 아니면 O(n√k - log n)쯤 된다고 함
->상당히 빠르고 안정적인 편이다.
->Html 문서에 쓰인다고 하는데 무슨소린지 모르겠다.

2006 by Michael A. Bender, Martín Farach-Colton, Miguel Mosteiro
도서관 정렬(Library Sort)

->삽입정렬의 변종이다.

??? by ???
기수정렬(Radix Sort)

->특정 진수의 자릿수를 기반으로 어떻게 쪼개고 합치면서 정렬하는 알고리즘이다.
->아주 다양한 바리에이션이 존재한다.

??? by ???
버킷정렬(Bucket Sort)

->

??? by ???
보고정렬(Bogo Sort)

->막 랜덤으로 섞는 정렬이다.
->당연히 느려터졌고, 보통장난용으로나 사용하는데. 유전 알고리즘과 결합하면 괜찮다고 한다.