1. 알고리즘별 정의, 장점, 단점 정리
| 종류 | 정의 | 장점 | 단점 | 이용 |
| 버블 정렬(Bubble Sort) | 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면 맨 끝까지 정렬하는 방식 | 구현이 간단 코드가 직관 |
정렬 시간이 오래 걸림 | 이미 정렬된 데이터를 정렬 시에 빠르다(반대로 역순 배열은 가장 느림) |
| 선택 정렬(Selection Sort) | 최소 값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식(반복) | 구현이 간단 비교하는 횟수에 비해 교환이 적게 일어남 버블 정렬보다 빠름 |
정렬 시간이 오래 걸림 | 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적(역순 정렬) 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬할 시 최악 |
| 삽입 정렬(Insertion Sort) | 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신위 위치를 찾아 삽입하는 방식 | 최선의 경우 O(N)으로 정렬 가능 | 최악의 경우 O(N^2)이 걸림 | 다른 정렬 알고리즘의 일부로 쓰임 이미 정렬된 경우 아주 최고의 정렬 알고리즘(탐색을 제외한 오버헤드가 매우 적음) |
| 합병 정렬(Merge Sort) | 작은 단위로 잘게 쪼개어 작은 단위부터 정렬해서 정렬된 단위들을 계속 병합해가면서 정렬하는 방식 | 항상 O(NlogN)으로 일정한 속도로 정렬 | 추가적인 메모리 공간 필요(임시 배열에 원본 맵을 계속해서 옮겨주면서 정렬하는 방법) | 순차적인 비교로 정렬하기에 LinkedList의 정렬에 사용하면 효율적 크기가 큰 레코드 정렬 시 효율적 |
| 퀵 정렬(Quick Sort) | Pivot을 정하여 이 축의 값보다 작은 값은 왼쪽에 큰 값은 오른쪽으로 위치시킨뒤 왼쪽과 오른쪽의 수들을 다시 각각의 축으로 나누어져 축 값이 가장 작은 값이 될 때까지 정렬 | 평균 실행시간 O(NlogN)으로 빠른 편 | Pivot에 따라 성능 차이가 심함 최악의 경우 O(N^2)이 걸림 |
순차 접근이 아닌 임의 접근이기에 LinkedList를 퀵 정렬에 사용하면 성능이 좋지 않다 |
| 힙 정렬(Heap Sort) | 최대 힙을 만들고 루트 노드를 던지고 마지막 노드를 루트 노드 위치에 넣고 다시 최대 힙 만들기를 반복 | 항상 O(NlogN)으로 빠른 편 | 다른 O(NlogN)의 정렬법보다 오래 걸림 |
가장 크거나 가장 작은 값을 구할 때 최대 K만큼 떨어진 요소들을 구할 때 : 삽입 정렬을 개선 |
| 쉘 정렬(Shell Sort) | 삽입정렬의 개념을 확대하여 일반화한 정렬방법 | O(NlogN)의 정렬법보다 빠름 | 설정 간격에 따라 성능 차이가 심함 | 삽입 정렬을 보안한 알고리즘으로 삽입 정렬 시 삽입되어야할 위치가 현재 위치에서 상당히 멀리 떨이진 곳에 정렬을 해야만 하는 경우 쉘 정렬 사용 |
| 기수 정렬(Radix Sort) | 데이터의 비교를 통한 정렬이 아닌 분산 정렬을 이용한 정렬 방법으로 자릿수가 있는 데이터(정수, 문자열 등)에만 사용 가능 | O(N) 속도로 굉장히 빨리 정렬 가능 | '버킷'이라는 추가적인 메모리가 할당되어야 한다. 즉, 메모리가 생각보다 많이 소비 데이터 타입이 항상 일정해야함 구현을 위한 조건이 많이 붙음 |
자릿수가 있는 데이터를 정렬할 경우 |
| 계수 정렬(Counting Sort) | 비교하지 않는 정렬로 정렬하기 위한 요소들이 몇 개씩 있는지 세어서 적절한 위치에 선형 시간에 정렬하는 방법 | 적은 개수의 숫자를 정렬할 때 빠름 | 추가적인 메모리(숫자 개수를 저장할 공간, 결과를 저장할 공간)가 필요 가장 큰 숫자에 영향을 받는다는 점 |
특정 범위내에서 반복되는 정수인 많은 데이터의 경우에 효율적 (만약 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리) |
2. 알고리즘별 시간복잡도 및 공간 복잡도
| 종류 | 평균 | 최선 | 최악 | 공간 복잡도 |
| 버블 정렬(Bubble Sort) | O(N^2) | O(N^2) | O(N^2) | O(N^2) |
| 선택 정렬(Selection Sort) | O(N^2) | O(N^2) | O(N^2) | O(N) |
| 삽입 정렬(Insertion Sort) | O(N^2) | O(N) | O(N^2) | O(N^2) |
| 합병 정렬(Merge Sort) | O(NlogN) | O(NlogN) | O(NlogN) | O(NlogN) |
| 퀵 정렬(Quick Sort) | O(NlogN) | O(NlogN) | O(N^2) | O(NlogN) |
| 힙 정렬(Heap Sort) | O(NlogN) | O(NlogN) | O(NlogN) | O(NlogN) |
| 쉘 정렬(Shell Sort) | O(N^1.25) | O(N^1.25) | O(N^1.25) | O(N) |
| 기수 정렬(Radix Sort) | O(dN) / d는 최대값의 자릿수 | O(dN) | O(dN) | O(N) |
| 계수 정렬(Counting Sort) | O(N+k) | O(N+k) | O(N+k) | O(K) / K는 K 크기만큼의 배열을 만들어야 한다는 뜻 |
ETC
- 추가적인 메모리 할당이 불가능한 경우 병합 vs 큌 : 데이터가 최악인 것만 본다면 퀵 보다 병합 정렬이 훨씬 빠르지만 추가 메모리 할당이 없다면 병합 정렬은 사용 불가이기에 퀵을 써야한다
- 안정 정렬 : 중복된 값을 입력 순서와 동일하게 정렬하는 특성 ex) 삽입 정렬, 버블 정렬, 합병 정렬, 계수 정렬
- 불안정 정렬 : 중복된 값이 입력 순서와 동일하지 않게 정렬되는 특성 ex) 선택 정렬, 퀵 정렬, 힙 정렬
- 기본으로 탑재 되어있는 언어의 라이브러리 중 정렬은 시간 복잡도가 보통 NlogN으로 잘 판단하여 사용할 것.