목차
1. 선택정렬(Selection Sort)
2. 버블정렬(Bubble Sort)
3. 삽입정렬(Insertion Sort)
4. 퀵 정렬(Quick Sort)
5. 병합 정렬(Merge Sort)
1. 선택정렬(Selection Sort)
- 처음부터 끝까지 검사하여 가장 작은 값이 맨 앞으로 오도록 하는 정렬 알고리즘
- O(N^2)의 시간복잡도를 가진다.
- N * (N + 1) / 2
=> N^2
- N * (N + 1) / 2
// 가장 작은 값을 찾았다면 그것과 해당 index위치의 값과 위치를 바꾼다.
1) 1 10 5 8 7 6 4 3 2 9
2) 1 10 5 8 7 6 4 3 2 9
3) 1 2 5 8 7 6 4 3 10 9
4) 1 2 3 8 7 6 4 5 10 9
5) 1 2 3 4 7 6 8 5 10 9
...2. 버블정렬(Bubble Sort)
- 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다.
- 정렬 알고리즘 중 가장 구현이 쉽지만 가장 효율성이 떨어진다.
- O(N^2)의 시간복잡도를 가진다.
- N * (N + 1) / 2
=> N^2
- N * (N + 1) / 2
// 결과적으로 가장 큰 값을 가장 뒤에 위치시키는 알고리즘이다.
1) 1 10 5 8 7 6 4 3 2 9
2) 1 5 7 6 4 3 2 8 9 10
3) 1 5 6 4 3 2 7 8 9 10
4) 1 5 4 3 2 6 7 8 9 10
5) 1 4 3 2 5 6 7 8 9 10
...< 버블정렬과 선택정렬 비교 >
- 버블정렬과 선택정렬은 같은 시간복잡도를 가지지만 실제로는 버블정렬이 훨씬 느리다.
- 버블정렬은 비교 후 즉시 두 값의 위치를 바꾸는 연산을 수행하지만
- 선택정렬은 가장 작은 값을 찾은 후 마지막에만 두 값의 위치를 바꾸는 연산을 수행하기 때문이다.
3. 삽입정렬(Insertion Sort)
- 각 숫자를 적절한 위치에 삽입한다.
- 위 두 정렬방식을 무조건 위치를 바꾸는 방식이라고 한다면
- 삽입정렬은 '필요할 때만' 위치를 바꾸는 방식이다.
- O(N^2)의 시간복잡도를 가진다.
- O(N^2)의 시간복잡도를 가지는 세 정렬 중 가장 효율적이다.
- 특히 거의 정렬이 되어 있을수록 삽입정렬의 속도가 빠르다.
// "앞이 정렬 되어 있다고 가정하고", 어느 위치에 들어가야 하는지를 판별해서 위치를 바꿔준다.
// 여기까지 정렬이 이루어졌고
1) 1 5 10 8 7 6 4 3 2 9
// 다음 정렬 대상인 8은 _들 중 어느 위치에 들어가야 하는지 판별한다.
2) _ 1 _ 5 _ 10 _ 8 7 6 4 3 2 9
// 아래가 옳은 정렬이다.
3) 1 5 8 10 7 6 4 3 2 9
// 위 과정을 나머지 7 6 4 3 2 9에 대해서도 수행한다.4. 퀵 정렬(Quick Sort)
- 분할 정복 알고리즘을 이용한다.
- 특정 값을 기준으로 큰 숫자와 작은 숫자를 교환한 후에 배열을 반으로 나눈다.
특정 값: pivot 이라고 한다.
// 가장 앞의 값을 피벗값으로 설정한다.
3 7 8 1 5 9 6 10 2 4
피벗값: 3
1) 왼쪽에서 오른쪽으로 이동하며 피벗값(3)보다 큰 값을 선택한다. : 7
2) 오른쪽에서 왼쪽으로 이동하며 피벗값(3)보다 작은 값을 선택한다. : 2
3) 선택된 큰 값과 작은 값의 위치를 바꾸어 준다.
3 2 8 1 5 9 6 10 7 4
// 위 과정 반복
3 2 1 8 5 9 6 10 7 4
4) 반복 중 큰 값의 index가 작은 값의 index보다 크다면 : 1, 8
작은 값(1)을 피벗값(3)과 위치를 바꾼다.
1 2 3 8 5 9 6 10 7 4
5) 이미 정렬이 된 3을 기준으로 왼쪽(1, 2)과 오른쪽(8, 5, 9, 6, 10, 7, 4)를 다시 정렬해준다.
각 피벗값: 1, 8- O(N * logN)의 평균 시간복잡도를 가진다.
- 그러나 최악의 경우에는 O(N^2)의 시간복잡도를 가진다.
이미 정렬이 되어 있는 경우에 그러하다. 이 경우 삽입정렬이라면 빠르게 풀어낼 수 있다.
- 보통 이용하는 library의
sort()함수는 이 최악의 경우에도 O(N * logN)의 시간복잡도를 가지도록 구성되어 있다.
5. 병합 정렬(Merge Sort)
- 분할 정복 알고리즘을 이용한다.
- 퀵 정렬과 마찬가지로 O(N * logN)의 평균 시간복잡도를 가진다.
- 일단 반으로 나누고 나중에 합쳐서 정렬한다.
// 일단 절반씩 나눈다.
7 6 5 8 3 5 9 1
// 정렬1
67 58 35 19
// 정렬2
5678 1359
// 정렬3
13556789- 병합정렬 구현시, 정렬에 사용되는 배열은 반드시 전역변수로 선언해야 한다.
- 함수 내에서 배열을 선언하게 된다면 매 번 배열을 선언해야 한다는 점에서 메모리 자원의 낭비가 커질 수 있다.
- 기존의 데이터를 담을 추가적인 배열 공간이 필요하다는 점에서 메모리 활용이 비효율적이라는 문제가 있다.
cornchip