기록
[알고리즘] 선택정렬, 버블정렬, 삽입정렬 - O(N^2) 본문
정렬 알고리즘
1. 선택 정렬 (Selection Sort)
1 10 5 8 7 6 4 3 2 9
이걸 오름차순으로 정렬할 때, 가장 작은 걸 골라(select) 맨 앞으로 가져오는 알고리즘이다.
Source Code
#include <stdio.h>
int main(void){
int i, j, min, index, temp;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i = 0; i < 10; i++){
min = 9999; //가장 큰 숫자
for(j = i; j < 10; j++){
if(min > array[j]){
//min값을 i번째 부터 마지막 원소까지 검사한다.
min = array[j];
index = j;
}
temp = array[i]; //원래 i번째 있던 값을 temp에 저장
array[i] = array[index]; //최솟값을 i번째로 대입
array[index] = temp; //temp를 바꾼 자리에 저장
}
}
}
<시간 복잡도 - 선택 정렬>
10 + 9 + 8 + ... + 1
=> 10 * (10 + 1) / 2 = 55
=> N * (N + 1) / 2
=> O(N * N)
=> O(N^2)
선택 정렬은 시간 복잡도가 N제곱 이므로 비효율적인 알고리즘이다.
2. 버블 정렬 (Bubble Sort)
1 10 5 8 7 6 4 3 2 9
이걸 오름차순으로 정렬할 때, 바로 옆에 있는 수와 비교해 큰 수를 뒤로 보내는 것을 계속 반복한다.
정렬 알고리즘 중에서 가장!! 비효율적인 알고리즘이다.
이유: 위의 선택 정렬과 비교해보면 for - for 문 안에서 대입하는 횟수가
선택 정렬은 min = array[j]로 1번이지만
버블 정렬은 swap을 하기 때문에 3번이기 때문에
시간복잡도는 같아도, 실직적인 수행 시간에서 차이가 난다.
Source Code
#include <stdio.h>
int main(void){
int i, j, temp;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};ay
for(i = 0; i < 10; i++){ //원소의 개수만큼 반복
for(j = 0; j < 9-i; j++){ //마지막 index부터 가장 큰 수를 뒤로 보내는 것을 반복
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1]
}
}
}
}
<시간복잡도 - 버블정렬>
10 + 9 + 8 + ... + 1
=> 10 * (10 + 1) / 2 = 55
=> N * (N + 1) / 2
=> O(N * N)
=> O(N^2)
3. 삽입정렬 (Insertion Sort)
1 10 5 8 7 6 4 3 2 9
삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결한다. 다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면, 삽입 정렬은 '필요할 때만' 위치를 바꾸게 된다.
시간복잡도 O(N^2)인 정렬 알고리즘 중에서 가장 빠르다.
각 숫자를 삽입할 때, 이미 앞에 있는 숫자들은 정렬이 되어있기 때문에 빠르다.
그렇다고 엄청 빠른 건 아니다.
Source Code
#include <stdio.h>
int main(void){
int i, j, temp;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i = 0; i < 10; i ++){
j = i;
while(array[j] > array[j]+1){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
j--;
}
}
return 0;
}
<시간복잡도 - 삽입정렬>
10 + 9 + 8 + ... + 1
=> 10 * (10 + 1) / 2 = 55
=> N * (N + 1) / 2
=> O(N * N)
=> O(N^2)
4. 퀵정렬 (Quick Sort)
퀵 정렬은 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN)이다.
퀵 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.
일반적으로 퀵 정렬에는 기준 값이 있는데, 이를 피벗(Pivot)이라고 한다. 보통은 피벗 값을 첫번째 원소로 정한다.
우리는 다음과 같이 1이 피벗 값으로 설정됐다고 생각해보자.
1 10 5 8 7 6 4 3 2 9
이 경우 1보다 큰 숫자를 왼쪽부터 찾고, 동시에 1보다 작은 숫자를 오른쪽부터 찾는다.
이 때 1보다 큰 숫자로는 바로 10이 있겠고, 1보다 작은 숫자가 1의 오른쪽에 없기 때문에 9, 2, 3, 4 ... 를 지나 결국 피벗값 1에 도달한다.
Source code
#include <stdio.h>
int number = 10;
int data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
void quickSort(int *data, int start, int end) {
if (start >= end) { //원소가 1개인 경우
return;
}
int key = start; //키(pivot)는 첫 번째 원소
int i = start + 1; //왼쪽 출발 지점
int j = end; //오른쪽 출발 인덱스
int temp;
while(i <= j) { //i와 j가 엇갈릴 때 까지 반복
while(data[i] <= data[key]) { //키값보다 왼쪽에 있는게 클 때까지
i++;
}
while(data[j] >= data[key] && j > start) {
j--;
}
if(i > j) { //'현재' 엇갈린 상태면 키 값과 교체
temp = data[j];
data[j] = data[key];
data[key] = temp;
} else {
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
//재귀함수 이용해서
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
int main(void) {
quickSort(data, 0, number - 1);
}
퀵 정렬 범위 설정
quickSort()에서 오른쪽부터 키값보다 작은 값을 찾을 때
while의 조건문에 j > start 가 있는 이유는 만약 키 값보다 작은 값이 오른쪽에 없는 경우 더 넘어가지 않고 키값 다음 인덱스에서 검사를 멈추게 하기 위해서이다.
그렇다면 위에서 왼쪽부터 키 값보다 큰 값을 찾는 while문에는 왜 그런 범위를 설정하지 않아도 되는걸까?
그 이유는 왼쪽부터 키값으로 도달한 경우 i와 j가 엇갈려 제일 바깥 while이 종료 되기 때문이다.
퀵 정렬의 한계
그러나, pivot 값을 잘못 정할 경우 퀵정렬의 최악 시간 복잡도는 O(N^2)가 돼버리기도 한다.
이미 정렬이 되어있는 경우를 생각해보자.
1 2 3 4 5 6 7 8 9 10
pivot값: 1
오른쪽부터 10번이나 비교를 해도 작은 값을 찾지 못하고
1 2 3 4 5 6 7 8 9 10
이렇게 마무리된다.
...
이런식으로 10번, 9번, ... 연산을 하게 되어 O(N^2)가 되는 것이다.
+) 내림차순으로 바꾸고 싶을 경우 숫자를 정렬하는 방향이 반대가 되는 것이기 때문에 왼쪽을 오른쪽으로, 오른쪽을 왼쪽으로 바꿔주면 된다.
'공부 > Algorithm' 카테고리의 다른 글
BinaryTree (0) | 2020.09.30 |
---|---|
Searching (0) | 2020.09.30 |
[알고리즘] 동적 계획법 (Dynamic Programming) (0) | 2020.08.11 |
[알고리즘] 깊이 우선 탐색(Depth-First Search)와 너비 우선 탐색(Breadth-First Search) (0) | 2020.07.22 |
Greedy Algorithm (탐욕 알고리즘) (0) | 2020.07.05 |