선택 정렬
선택 정렬(Selection Sort)는 가장 작은값을 찾아 현재 위치와 교환하는 방식이다.
특징
- 교환 횟수가 적다
- 비교 횟수가 많다
- 데이터가 많으면 성능이 떨어진다
예시
선택 정렬의 동작 방식
5 9 7 4
라는 배열이 있을때
1바퀴
4 9 7 5
2바퀴
4 5 7 9
3바퀴
4 5 7 9이런식으로 동작하는데, 전체 배열을 돌면서 최소값을 또 한번 찾아야 하므로, 시간 복잡도는 O(n^2)가 된다.
버블 정렬
버블 정렬(Bubble Sort)는 인접한 두 데이터의 크기를 비교하여 더 작은값(오름차순 기준일때)이 뒤에 있으면 교환하는 알고리즘이다.
특징
- 구현이 쉽다
- 데이터가 많으면 성능이 떨어진다
- 실제로 사용 X
예시
버블 정렬의 동작 방식
4 3 2 1
라는 배열이 있을때
1바퀴
3 2 1 4
2바퀴
2 1 3 4
3바퀴
1 2 3 4이런 식으로 한칸씩 옆으로 옮기는 버블정렬의 특성상, 시간복잡도는 O(n^2)가 된다.
하지만, 최선의 경우에선 딱 한바퀴만 돌아도 정렬이 되기때문에 O(n)이 된다.
삽입 정렬
삽입 정렬(Insertion Sort)은 앞의 원소들과 비교하여 값이 크면 뒤로, 작으면 앞으로(오름차순 기준) 삽입하는 알고리즘이다.
특징
- 정렬이 되어있는 데이터에 추가하여 사용할시 효과적이다
예시
삽입 정렬의 동작 방식
4 3 2 1
라는 배열이 있을때
1바퀴
3 4 2 1 //4보다 3이 작음
2바퀴
2 3 4 1 //3보다 2가 작음
3바퀴
1 2 3 4 //2보다 1이 작음첫번째 인덱스인 4를 기준으로 비교하여 4보다 작으면 왼쪽, 크면 오른쪽으로 삽입한다.
시간복잡도는 평균 O(n^2)이다.
병합 정렬
병합 정렬(Merge Sort)는 배열을 절반으로 나눈 후에 각각 정렬하고 합치는 방식이다.
특징
- 어떤 상황에서든 성능이 같다
- 주어진 데이터만큼의 추가 메모리가 필요하다
- 대용량 데이터를 처리하는데 용이하다
예시
병합 정렬의 동작 방식
4 3 2 1
라는 배열이 있을때
4 3 | 2 1 로 분할
3 4 | 1 2 로 정렬
1 2 3 4 로 병합 //두개의 배열에서 더 작은값을 앞으로 정렬시간복잡도는 최선, 최악, 평균 전부 O(n log n)의 성능을 보장한다.
퀵정렬
퀵 정렬(Quick Sort)은 기준값(Pivot)을 기준으로 삼아 작은 값과 큰 값으로 분할하여 정렬하는 알고리즘이다. Pivot은 임의로 정해도 상관없지만 최악의 상황을 방지하기위해 보통은 중앙값을 사용한다.
또한, Pivot값을 토대로 큰값과 작은값을 swap하고, 큰값과 작은값을 가리키는 포인터를 한칸씩 이동한다.
특징
- 평균적으로 가장 빠른 정렬이다.
- 실제 자주 사용하는 정렬이다.
- Pivot 값에 따라 성능이 천차만별이다.
예시
퀵 정렬의 동작 방식
5 4 3 2 1
라는 배열이 있을때
Pivot=3으로 지정
1바퀴
2 1 3 5 4 //3을 기준으로 양옆값 swap
2바퀴
1 2 3 4 5 //왼쪽 그룹인 [2, 1]과 오른쪽 그룹인 [5, 4]의 정렬 진행시간복잡도는 평균 O(n log n)이며 Pivot을 잘못선택하여 배열이 한쪽으로 치우치게 된다면 최악의 경우로 O(n^2)이다.
힙 정렬
힙 정렬(Heap Sort)은 최대값 또는 최소값을 꺼내어 정렬하는 방식이다.
힙 정렬은 트리 구조를 사용하여, 최대값과 마지막 원소를 교환하는 방식으로 사용된다.
특징
- 추가 메모리가 거의 필요없다.
- 성능이 평균, 최악, 최선 모두 일정하다
예시
힙 정렬의 동작 방식
4 3 2 1
라는 배열이 있을때
4
/ \
3 2
/
1
최대 값인 4와 마지막원소 1을 교환한다
1 3 2 4
그 후, 이미 정렬이 완료된 4를 제외하고 힙을 재구성한다.
1
/ \
3 2
3
/ \
1 2
루트값은 3이므로 마지막 원소인 2와 교환한다.
2 1 3 4
마지막으로 1과 2로도 힙을 재구성하고, 변경해주면 정렬이 완료된다.
1 2 3 4이런 식으로 한칸씩 옆으로 옮기는 버블정렬의 특성상, 시간복잡도는 O(n^2)가 된다.
하지만, 최선의 경우에선 딱 한바퀴만 돌아도 정렬이 되기때문에 O(n)이 된다.
셸 정렬
셸 정렬(Shell Sort)은 삽입 정렬을 개선한 알고리즘으로서, 일정 간격(Gap)으로 떨어진 원소들을 먼저 정렬한 뒤에 간격을 줄여가며 정렬한다.
특징
- 삽입 정렬보다 빠르다
- Gap 선택에 따라 성능이 천차만별이다
예시
셸 정렬의 동작 방식
8 7 6 5 4 3 2 1
Gap = 4
8 7 6 5 | 4 3 2 1 //정렬
4 3 2 1 8 7 6 5
Gap = 2
4 3 | 2 1 | 8 7 | 6 5 //정렬
2 1 4 3 6 5 8 7
Gap = 1
1 2 3 4 5 6 7 8셸 정렬의 시간복잡도는 Gap에 따라 달라지며 최악의 경우 O(n^2) 평균적으로는 O(nlogn)이다.
