[자료구조] 정렬(Sort)

정렬 알고리즘의 성능 비교

알고리즘	최선	평균	최악
삽입 정렬	O(n)	O(n^2)	O(n^2)
선택 정렬	O(n^2)	O(n^2)	O(n^2)
버블 정렬	O(n^2)	O(n^2)	O(n^2)
쉘 정렬	O(n)	O(n^1.5)	O(n^1.5)
퀵 정렬	O(nlog 2n)	O(nlog 2n)	O(n^2)
힙 정렬	O(nlog 2n)	O(nlog 2n)	O(nlog 2n)
합병 정렬	O(nlog 2n)	O(nlog 2n)	O(nlog 2n)
기수 정렬	O(dn)	O(dn)	O(dn)

(표 : http://wonjayk.tistory.com/225 )

* 안정성 이 있는 정렬 : 같은 값을 가진 데이터의 순서가 정렬 후에도 바뀌지 않고 그대로 유지하는 정렬

  ex) 삽입정렬, 버블정렬, 합병정렬, 기수 정렬

1. 삽입(Insertion) 정렬

: 자기보다 앞에 있는 원소들을 살펴서 순서가 어긋나 있으면 자신을 거기로 옮기고, 원소들을 뒤로 한 칸씩 밀어냄

 > 선택 정렬보다 두 배 정도 빠르다고 함!

 > 어느 정도 정렬 된 자료인 경우 매우 적합, 이미 정렬된 자료에 새 자료 추가시에도 매우 좋음.

2. 선택(Selection) 정렬

: 가장 큰 값을 선택해서 리스트의 끝으로 옮김

 > 가장 쉽고 직관적임

 > 버블 정렬보다 2~3배 빠르다고 함!

3. 버블(Bubble, 거품) 정렬

: 한원소와 바로 옆 원소를 비교하여 위치를 맞바꾼다! 뽀글뽀글 하고 움직임

4. 쉘(Shell) 정렬

: 삽입정렬을 일정한 간격으로 수행한 뒤 전체적으로 대부분 정렬되어있는 결과를 다시 삽입정렬로 종합

 > 삽입정렬의 응용으로, 삽입정렬의 성능과는 비교할 수 없을 정도로 빠름

5. 퀵(Quick) 정렬

: 피벗을 선택해 그 값을 기준으로 자료를 양쪽으로 나눔. 나눠진 자료에서 다시 피벗을 선택해 또 나눔... 반복

6. 합병(Merge, 병합) 정렬

: 정렬된 작은 부분을 합쳐 다시 정렬(자료가 하나밖에 없으면 그건 정렬된 상태잖아?)

 > 데이터 전체 크기만한 메모리가 더 필요함

7. 힙(Heap) 정렬

: 이진 완전 나무(ㅋㅋㅋ Complete Binary Tree, 완전 이진트리)를 사용

 > 부가 메모리 필요없음

8. 기수(Radix) 정렬

: 자리수 기준으로 차례차례 정렬( 천자리>백자리>십자리>일자리...내 일자리는 어디에ㅜㅜ)

 > 비교연산 X

 > 기수 테이블의 크기만한 메모리가 필요함, 정수에만 적용가능

** 참조 할만한 페이지 : http://laonatti.tistory.com/115 // 되게 감탄하면서 재미있게 적어둠. 재밌음