Selection sort 는 in-place comparison sort 로 구현되는 정렬알고리즘이다. 이 알고리즘은 O(n2)의 복잡도를 가진다. 데이터의 양이 많을 경우 비효율적인 알고리즘이다. bubble sort가 동일한 복잡도를 보여준다. 가장 큰 (혹은 가장 작은) 값을 선택 (selection)해서 치환하는 과정을 거치기 때문에, Selection이라는 이름이 붙었다.
이 알고리즘은 다음과 같이 작동한다.
리스트에서 가장 작은 값을 찾는다.
찾아낸 가장 작은 값을 첫번째 위치에 복사한다.
남아 있는 리스트에서 위의 1,2 과정을 되풀이 한다. (시작 위치가 1만큼 증가할 것이다)
다음 visual sort 프로그램을 이용하면, 위의 과정을 쉽게 이해할 수 있을 것이다. 아래의 경우 가장 큰 값을 기준으로 정렬하고 있다.
과정이 단순한 만큼, 매우 쉽게 코드로 구현가능 하다.
#include <stdio.h>
void selection(int *list, int len)
{
int i = 0;
int j = 0;
int idx = 0;
int min = 1000;
for (i = 0; i < len ; i++)
{
min = 1000;
for (j = i; j < len; j++)
{
if (list[j]< min)
{
min = list[j];
idx = j;
}
}
// swap
min = list[idx];
list[idx] = list[i];
list[i] = min;
}
}
int main(int argc, char **argv)
{
int i = 0;
int data[] = {5, 8, 1, 9, 3, 4, 7, 2, 6, 0};
int len;
len = sizeof(data)/sizeof(int);
selection(data, len);
for (i =0; i < len; i++)
{
printf("%d\n", data[i]);
}
}
- 리스트에서 가장 작은 값을 찾는다.
- 찾아낸 가장 작은 값을 첫번째 위치에 복사한다.
- 남아 있는 리스트에서 위의 1,2 과정을 되풀이 한다. (시작 위치가 1만큼 증가할 것이다)
다음 visual sort 프로그램을 이용하면, 위의 과정을 쉽게 이해할 수 있을 것이다. 아래의 경우 가장 큰 값을 기준으로 정렬하고 있다. 과정이 단순한 만큼, 매우 쉽게 코드로 구현가능 하다.#include <stdio.h> void selection(int *list, int len) { int i = 0; int j = 0; int idx = 0; int min = 1000; for (i = 0; i < len ; i++) { min = 1000; for (j = i; j < len; j++) { if (list[j]< min) { min = list[j]; idx = j; } } // swap min = list[idx]; list[idx] = list[i]; list[i] = min; } } int main(int argc, char **argv) { int i = 0; int data[] = {5, 8, 1, 9, 3, 4, 7, 2, 6, 0}; int len; len = sizeof(data)/sizeof(int); selection(data, len); for (i =0; i < len; i++) { printf("%d\n", data[i]); } }Recent Posts
Archive Posts
Tags