Joinc Wiki: 정렬알고리즘 : Selection Sort

Facebook Joinc 그룹 Joinc QA 사이트

현재위치 : 미니사이트>Database>algorithm>Selection_Sort

joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.

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]); 
  } 
}

뇌자극 QA 뇌자극 에러 및 수정목록 총 페이지 수 : 3224 전체 함수/용어사전 구글검색방법 구글 맞춤검색	Facebook Joinc 그룹 Joinc QA 사이트 현재위치 : 미니사이트>Database>algorithm>Selection_Sort Tweet joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다. 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]); } }