시간 복잡도 & 공간 복잡도
- 시간 복잡도 : 알고리즘의 수행에 필요한 시간- 공간 복잡도 : 알고리즘의 수행에 필요한 기억장치(메모리)의 크기
| 알고리즘 | 평균 시간 복잡도 | 공간 복잡도 |
|---|---|---|
| 선택 정렬 | O(N^2) | O(N^2) |
| 버블 정렬 | O(N^2) | O(N) |
| 삽입 정렬 | O(N^2) | O(N^2) |
| 병합 정렬 | O(NlogN) | O(NlogN) |
| 퀵 정렬 | O(NlogN) | O(NlogN) |
| 힙 정렬 | O(NlogN) | O(NlogN) |
| 셀 정렬 | O(N^1.5) | O(N) |
| 선택 정렬
- 앞쪽부터 정렬하는 방식으로 주어진 배열에서 가장 작은 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬한다.
- 정렬 방식이 배열 내 최솟값을 찾아 선택하여 정렬한다는 뜻에서 붙여진 명칭이다.
| 버블 정렬
- 첫 번째 원소부터 인접한 우측 원소와 비교하며 자리를 바꾸면서 맨 끝부터 정렬하는 방식이다.
- 정렬 방식이 마치 물 속에서 올라오는 물방울 같다고 붙여진 명칭이다.
| 삽입 정렬
- 버블 정렬의 비효율성을 개선하기 위해 등장한 방식으로 i번째 원소를 정렬된 상태의 앞부분과 비교하며 적절한 위치에 삽입하는 방식이다.
- 정렬 방식이 정렬된 상태의 앞부분과 비교하여 적절한 위치에 삽입한다고 붙여진 명칭이다.
| 병합 정렬
- 배열을 작은 단위로 쪼개어 정렬한 결과를 합치면서 전체를 정렬하는 방식이다.
- 작은 단위로 쪼갠 배열을 저장할 공간을 사용하기에 추가적인 메모리가 필요하다.
| 퀵 정렬
- 하나의 pivot을 정하여 해당 값보다 작은 값은 좌측에, 큰 값은 우측에 위치시킨 뒤,
좌측과 우측에 pivot을 다시 정한 뒤 작은 값은 좌측에, 큰 값은 우측에 정렬하는 방식이다.- 대부분 내장 라이브러리에서 존재하는 정렬 함수는 퀵 정렬 알고리즘이 사용된다.
| 힙 정렬
- 최대 힙 트리나 최소 힙 트리를 구성하여 정렬하는 방식이다.
- 여러 개의 값 중에서 최댓값이나, 최솟값을 빠르게 찾기 위해 사용된다.
| 셀 정렬
- 삽입 정렬의 문제점을 해결하기 위해 등장한 정렬 방식으로 입력으로 들어온 배열을 간격이라고 하는 일정한 기준에 따라 분류한다.
- 이를 통해 연속적이지 않은 여러 개의 부분 배열을 생성한 후 각 배열을 삽입 정렬로 정렬하는 방식이다.
