가장 간단한 버블정렬, 보기에도 답답하고 느림

버블정렬은 index와 index+1의 요소를 비교해서 교환해나가며 정렬

BigO로는 O(n²) , 말그대로 최악의경우, 최선의 경우 전부 O(n²)이다






선택정렬, 순차적으로 탐색해 나가며 가장 작은 요소 '선택'하여 맨앞으로 교환한다.

BIGO로는 최선 최악 둘다 O(n²), 

다만 교환 연산이 N번당 한번밖에 없으므로 개찐도찐이지만 실제적으로는 버블보다 약간 빠르다.


삽입정렬, 삽입정렬은 Index 번째 요소를 Index -1 부터 0번까지 탐색하되,

자기보다 작은 수를 만나면 거기다 '삽입'한다.

사실 Index 자체가 없는 링크드 리스트 구조에서는 삽입정렬이 구현하기 편리한편,

최악의경우 O(n²) 이지만, 버블정렬, 선택정렬과 다르게 탐색을 '이미 정렬된부분 (초록색부분)을 탐색하므로

O(n²) 이지만 최선의 경우 (어느정도 정렬이 되어있는 경우) n번만에 정렬가능해서 

정렬을 자주하는 배열에게는 그어떤 정렬보다 빠르다.




셸정렬은 도널드 셸이라는 사람이 고안한 정렬방식이다. 

선택정렬이 어느정도 정렬되어있는 상태에서 최선의 효과를 두는점을 현명하게 이용한다.

셸정렬의 탐색을  주변인덱스가 아닌, 어느정도 간격을 두고 셸정렬을 하며, 마지막에는 그냥 셸정렬은 한다.

쉽게말하면 ( index++ 가 아닌 index += gap )으로 탐색한다. 물론 한번의 탐색이 끝나면 gap /= 2로 줄인다.

빅오로 따지면 이론상 O(n²)이지만 실제적으로 O(n1.25) 정도 된다고 한다.





머지정렬, 대표적인 분할 정복방식의 정렬이다.

영역을 좌,우로 2씩 나눠가며 분할한후,

마지막 분할뒤 좌, 우를 비교하며 임시버퍼에 집어넣어 정렬한다.


머지정렬은  O( n log n )으로 빠른 정렬방식이긴 하지만, 

분할 깊이가 깊어질수록 스택을 사용하는 오버헤드도 있고,

같은 크기의 임시버퍼가 필요하기 때문에 다른 정렬방식과 달리 추가적인 메모리도 필요하다.





퀵정렬, 말그대로 빠른 정렬이다.

퀵정렬은 분할은 하지만 분할->정복방식은 아니다.


퀵정렬은 영역을 머지정렬과 다르게 분할하기 전에 먼저 기준을 세운다. (보통 Pivot 이라고 부른다 )

피봇을 선택하는것은 보통의 경우, 맨처음요소나 맨끝요소를 선택한다.


퀵정렬의 핵심은 

1. 피봇의 위치를 확정시키고 

2. 상대적으로 피봇보다 작은것은 왼쪽에, 큰것은 오른쪽에 두는것 이다.

따라서 영역을 ->, <-으로 탐색하다가 왼쪽 탐색지점이 오른쪽보다 크면 요소를 교환하며, (2번과정)

마지막으로 탐색지점이 서로 교차가 되면 피봇과 교차지점을 요소를 교환한다. (1번과정)


퀵정렬도 평균으로 BigO로  O( n log n )이다. 그러나 2번과정이 길어질경우 성능은 극도로 떨어지게 된다.

2번과정이 길어지는 경우는 '이미 정렬되어있는' 상태일 경우 길어질수밖에 없다.

따라서 퀵정렬은 같은 배열을 자주 정렬하는 용도로 쓰기에는 부적합하다.




힙정렬, 힙정렬은 이진트리중 하나인 (힙트리)로 정렬하는 방식이다.

힙트리 최소, 최대값을 찾기 쉽게 구현한 트리고, 배열로도 힙트리의 규칙을 만들수 있다.


구현방법은

1. 힙트리를 만든다.

2. 힙트리의 맨앞요소를 맨뒤에 넣는다.

3. 나머지 구간에서 다시 힙트리를 만든다.


결론-> 결국 힙트리만 만들주 알면 된다

참고로 대부분 라이브러리에 있는 정렬은 힙정렬과 퀵정렬을 혼합해서 만든다고 한다.





마지막으로 기수정렬
기수정렬은 자리수대로 정렬하는 정렬 방법이다.

보통은 큐 10개를 만들고 각자리 숫자의 큐에 집어넣고, 다시 꺼낸다.


1. 1의 자리순서대로 정렬

2. 1의 결과를 10의 자리 순서대로 정렬

3. 2의 결과를 100의 자리 순서대로 정렬

.

.


이런식으로 하면 된다. 

구현도 간단하고 성능도 좋다.  BIGO로는 N번이면 된다.

실제적으로는 배열의 숫자중 가장큰수의 최대자리수 * N번이다. (예를들어 1000이면, 4N)

단, 기수정렬은 정수데이터를 기준으로만 정렬할수 있으므로 사용에 제약이 있다.