![[알고리즘] 정렬](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fp5RpT%2FbtqDE0IwGzn%2Fgt5M7ufPb4eeV5xlXFdkK1%2Fimg.png)
정렬은 왜 필요할까?
우리가 사전에서 단어를 쉽게 찾을 수 있는 것처럼 컴퓨터도 정렬되어 있는 데이터에서 보다 효율적으로 탐색할 수 있기 때문이다.
◆ Bubble Sort, 거품정렬
서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘
◇ 과정
- 1회전에 첫번째 원소와 두번째 원소를, 두번째와 세번째, 세번째와 네번째 ... 이런 식으로 비교하며 조건에 맞지 않다면 서로 교환한다.
- 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 제외되고, 2회전을 수행하고 나면 끝에서 두번째 원소까지는 정렬에서 제외된다. 이렇게 제외되는 원소가 늘어난다.
● 시간복잡도
데이터의 개수가 N이라 할 때, 비교횟수는 N-1, N-2, N-3, ... , 1이 되므로 총 N(N-1)/2.
즉, O(N^2) 만큼의 시간이 걸린다. 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 시간복잡도는 O(N^2) 으로 동일하다.
● 공간복잡도
주어진 배열안에서 교환(swap)을 통해, 정렬이 수행되므로 O(N)
○ 장점
- 구현이 간단하다.
- 제자리 정렬이라 다른 메모리 공간을 필요로 하지 않는다.
- 안정 정렬이다.
○ 단점
- 시간복잡도가 최선, 최악, 평균 모두 O(N^2)으로 굉장히 비효율적이다.
- 원소가 정렬된 자리로 가기 위해 교환 연산이 많이 일어난다.
◆ Selection Sort, 선택 정렬
해당 순서에 원소를 넣을 위치는 이미 결정되어 있고, 어떤 원소를 넣을지 선택하는 알고리즘
◇ 과정
- 주어진 배열 중에 최솟값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 정렬한다.
● 시간복잡도
비교횟수가 (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2이므로 O(N^2)이다. 최선, 평균, 최악의 경우 시간복잡도는 O(N^2) 으로 동일하다.
● 공간복잡도
주어진 배열안에서 교환(swap)을 통해, 정렬이 수행되므로 O(N)
○ 장점
- 구현이 간단하다.
- 정렬을 위한 비교는 많지만 실제 교환횟수는 Bubble Sort보다 적다.
- 정렬하고자 하는 배열 안에서 교환하는 방식, 즉 제자리 정렬이라 다른 메모리 공간을 필요로 하지 않는다.
○ 단점
- 시간복잡도가 O(N^2)으로 비효율적이다.
- 불안정 정렬이다.
◆ Insertion Sort, 삽입 정렬
2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘
◇ 과정
- 2번째 위치(index)에서 시작해 값을 temp에 저장한다.
- temp와 이전에 있는 원소들을 비교해가며 삽입해나간다.
- '1'로 돌아가 다음 위치의 값(index+1)을 temp에 저장하고, 반복한다.
● 시간복잡도
최악의 경우(역으로 정렬되어 있을 경우) O(N^2)이다.
모두 정렬이 되어있는 경우(최선), 한번씩 밖에 비교를 안하므로 O(N)의 시간복잡도를 갖는다.
최선의 경우 O(N)의 시간복잡도를, 최악과 평균의 경우 O(N^2)의 시간복잡도를 가지게 된다.
● 공간복잡도
주어진 배열안에서 교환(swap)을 통해, 정렬이 수행되므로 O(N)
○ 장점
- 구현이 간단하다.
- 대부분의 원소가 정렬되어 있는 경우, 매우 효율적일 수 있다.
- 제자리 정렬이라 다른 메모리 공간을 필요로 하지 않는다.
- 안정 정렬이다.
○ 단점
- 평균과 최악의 시간복잡도가 O(N^2)으로 비효율적이다.
◆ Quick Sort, 퀵 소트
분할 정복 알고리즘 중 하나.
피벗이라는 기준을 하나 선택한 다음, 피벗보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 보낸 뒤 다시 왼쪽, 오른쪽에서 각각 정렬하는 방식의 알고리즘.
◇ 과정
- 피벗 선택
- 오른쪽(j)에서 왼쪽으로 가면서 피벗보다 작은 수 찾음.
- 왼쪽(i)에서 오른쪽으로 가면서 피벗보다 큰 수 찾음.
- 각 인덱스 i, j에 대한 요소 교환
- 2,3,4번 과정 반복
- 더이상 2,3번 진행이 불가능 해지면 현재 피벗과 교환
- 이제 교환된 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 다시 정렬
● 시간복잡도
배열의 길이 N이 2의 거듭제곱이라 할 때, 순환호출의 깊이는 log₂N이다.
각 순환호출에서는 대부분의 레코드를 비교해야 하므로 평균 N번 정도 비교가 일어난다.
최선, 평균의 경우 O(Nlog₂N)
리스트가 계속 불균형하게 나누어지는 경우, 순환호출의 깊이가 N이 된다
최악의 경우 O(N^2)
● 공간복잡도
주어진 배열안에서 교환(swap)을 통해, 정렬이 수행되므로 O(N)
○ 장점
- 속도가 빠르다
- 추가 메모리 공간을 필요로 하지 않는다.
○ 단점
- 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 늘어난다.
- 해결방법 : 피벗을 선택할 때 중간 요소를 선택
◆ Merge Sort, 합병 정렬
요소를 쪼갠 뒤, 다시 합병시키면서 정렬해나가는 분할 정복 알고리즘 중 하나
◇ 과정
- 리스트의 길이가 1이나 0이면 이미 정렬된 것으로 본다.
- 아니면 정렬되지 않은 리스트를 반으로 나눠 두 부분리스트로 나눈다.
- 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬한다.
- 두 부분 리스트를 하나의 정렬된 리스트로 합병한다.
● 시간복잡도
순환호출의 깊이 = log₂N
비교횟수 = N
따라서 O(Nlog₂N) (최선, 평균, 최악 다)
● 공간복잡도
배열이면 추가적인 메모리 공간이 필요하다.
연결리스트면 제자리 정렬이 가능하다.
○ 장점
- 안정 정렬이다.
○ 단점
- 배열로 구현하면 추가 메모리 공간이 필요하다.
◆ Heap Sort, 힙 정렬
완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로 하는 정렬 알고리즘
최대 힙이나 최소 힙을 구성해 모든 원소를 넣었다가 빼는 방식으로 정렬한다.
내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
◇ 과정
- 최대 힙을 구성한다.
- 최대 힙의 루트값은 최대값이다. 최대값을 뺀다. 루트 값을 마지막 요소와 바꾼 후 힙을 재구성하고, 힙의 사이즈를 하나 줄인다. (=힙의 삭제과정과 같다.)
- 힙의 사이트가 1보다 크면 위 과정을 반복한다.
이와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬하는 것이 힙 정렬이다.
● 시간복잡도
힙 트리의 전체 높이가 log₂N, 요소의 개수가 N개 이므로, O(Nlog₂N)
최선, 평균, 최악 다 같다.
● 공간복잡도
Heap에서 N만큼의 공간을 차지하므로 O(N)
○ 장점
- 시간복잡도가 좋다.
- 가장 크거나 가장 작은 값을 구할 때 가장 유용하다.
○ 단점
- 불안정 정렬이다.
◆ 비교
| 최선 | 평균 | 최악 | 안정? 불안정? | |
| 거품 정렬 | O(N^2) | O(N^2) | O(N^2) | 안정 |
| 선택 정렬 | O(N^2) | O(N^2) | O(N^2) | 불안정 |
| 삽입 정렬 | O(N) | O(N^2) | O(N^2) | 안정 |
| 퀵 정렬 | O(Nlog₂N) | O(Nlog₂N) | O(N^2) | 불안정 |
| 합병 정렬 | O(Nlog₂N) | O(Nlog₂N) | O(Nlog₂N) | 안정 |
| 힙 정렬 | O(Nlog₂N) | O(Nlog₂N) | O(Nlog₂N) | 불안정 |
◆ 안정 정렬? 불안정 정렬?
동일한 값에 대해 정렬 후에도 기본 순서가 유지되는 정렬을 안정정렬이라 하고, 기본 순서가 유지되지 않는 정렬을 불안정 정렬이라 한다.
안정 정렬 : 버블, 삽입, 합병
불안정 정렬 : 선택, 퀵, 힙
'공부 > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조] 여러 자료구조들 (0) | 2020.04.23 |
|---|---|
| 자료구조 - 2. 리스트 (0) | 2019.10.10 |
| 자료구조 - 1. 재귀 (0) | 2019.10.10 |