소트의 종류

시간복잡도 정리

	최악	평균	최선
1. 삽입정렬	n^2	n^2	n
2. 선택정렬	n^2	n^2	n^2
3. 버블정렬	n^2	n^2	n^2
4. 퀵정렬	n^2	nlog(n)	nlog(n)
5. 힙정렬	nlog(n)	nlog(n)	nlog(n)
6. 병합정렬	nlog(n)	nlog(n)	nlog(n)

 

1. 삽입정렬

- 앞에서 부터 순차적으로 선택하고 적절한 위치에 삽입 하는 정렬 방법

- 시간복잡도

최악	평균	최선
n^2	n^2	n

 

2. 선택정렬

- 가장작은(혹은큰) 값부터 선택해서 순차적으로 나열하는 것

- 시간복잡도

최악	평균	최선
n^2	n^2	n^2

 

3. 버블정렬

- 인접한 두 값을 서로 비교하여 교체하는 작업을 앞에서 부터 순차적으로 진행

- 시간복잡도

최악	평균	최선
n^2	n^2	n^2

 

4. 퀵정렬

- 기준값을 정하고 그 기준값의 양쪽으로 큰값과 작은값을 나열하는 방식을 재귀적으로 적용

- 시간복잡도

최악	평균	최선
n^2	nlog(n)	nlog(n)

 

5. 힙정렬

- heap 자료구조로 만든 후 값을 하나씩 pop하여 정렬

- 시간복잡도

최악	평균	최선
nlog(n)	nlog(n)	nlog(n)

 

6. 병합정렬

- 둘 이상의 부분집합으로 나누고 이를 합치는 방식을 재귀적으로 적용

- 시간복잡도

최악	평균	최선
nlog(n)	nlog(n)	nlog(n)