정렬 알고리즘(Sort)
- 선택정렬 알고리즘 (Selection Sort)
선택정렬 알고리즘 (Selection Sort)
✍ 작은것들을 골라 앞으로 보내자 ✍
#include <stdio.h>
int main(void)
{
int i, j, min, index, temp;
// i,j -> 배열에있는 값을 반복적으로 탐색하는데 쓴다.
// min -> 최솟값
// index -> 가장 작은 원소가 위치하는 곳
// temp -> 특정한 두 숫자를 바꾸기 위한 공간
int array[10] = {1,10,5,8,7,6,9,4,3,2,};
for (i = 0; i < 10; i++)
{
min = 9999;
for (j = i; j < 10; j++)
{
if (min > array[j])
{
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for (i = 0; i < 10; i++)
{
printf("%d", array[i]);
}
return 0;
}✍ 빅오(Big-O)표기법 ✍
- 알고리즘이란 결국엔 어떠한 문제를 해결하기 위한 하나의 방법일 뿐이고 그 문제를 해결하기 위한 다양한 방법들 간의 효율성을 비교하기 위해 빅오(Big-O)표기법을 사용한다. 쉽게 말해 빅오표기법은 알고리즘의 효율성을 표기해주는 기술방법이고 알고리즘의 효율성은 데이터 개수(N)개가 주어졌을 때 덧셈,뺄셈,곱셈,나눗셈 같은 기본연산의 횟수를 의미한다.
✍ 빅오(Big-O)표기법의 수학적 정의✍
✍ 빅오(Big-O)표기법의 특징 ✍
-
상수항 무시 - 데이터 입력값이 충분히 크다고 가정했을때, 알고리즘의 효율성은 데이터 입력값에 영향을 받는것이므로 상수항은 무시한다.
➔ O(2N) = O(N) -
영향력 없는 항 무시 - 알고리즘의 효율성은 데이터 입력값인 N에 영향을 받기때문에 가장큰 영향력을 가진 고차항을 제외한 나머지 항은 무시한다.
➔ O(NN + 2N + 1) = O(NN)
✍ 빅오(Big-O)표기법 성능 비교 ✍
- Faster ➔ Slower
O(1) < O(log N) < O(N) < O(Nlog N) < O(NN) < O(2exp(N))
상수함수 ➔ 로그함수 ➔ 선형함수 ➔ 다항함수 ➔ 지수함수
상수함수 : Stack Push/Pop
로그함수 : Binary Tree, Quick Sort, Merge Sort, Heap Sort
선형함수 : for문
다항함수 : 다중for문, Insertion Sort, Bubble Sort, Selection Sort
지수함수 : 피보나치 수열
✍ Selection Sort 효율성 ✍
- 1~10까지 무작위로 순서가 정해진 수들을 몇번 정렬해야 오름차순으로 선택정렬할 수 있을까?
ex) 3, 1, 4, 9, 5, 6, 8, 10, 7, 2
위와 같이 정렬되있는 배열이 있다고 가정하자. 첫번째 위치에 1이 오기 위해서는 1부터 10까지 확인해야하므로 10번 확인을 해야하고 두번째 위치에 오는 2를 선택정렬시키기 위해서는 9번 확인을 해야한다. 이런식으로 1부터 10까지 정렬을 위해 필요한 연산은
- 10 + 9 + 8 + ... + 2 + 1
이므로 공차가 1인 등차수열과 같다. 그러므로 총 합은 항의 개수와 항들의 평균을 곱한 값인 10 x (10 + 1) / 2 와 같다. 따라서 총 55번의 비교연산을 거쳐야 선택정렬이 완료된다.
즉, 위와 같은 결과를 통해 선택정렬의 수행시간은 N x (N + 1) / 2 이다.
빅오 표기법을 이용해 다시 표기하면 상수항과 영향력 없는 항의 무시를 통해
O(N x N) 이 된다. 따라서 다항함수와 같은 빅오표기법이 되고 효율성이 좋은 알고리즘은 아닌것이 된다.
Hi