Selection Sort   선택 정렬

(2019-03-09)
1. 선택 정렬 (Selection Sort)

  ㅇ 매 반복 패스 마다,
  ㅇ 가장 큰/가장 작은 자료를 선택하고(찾아서, 위치를 기억하고 있다가),
  ㅇ 그 반복 패스가 끝나면, 이를 선두로 옮기는(교환하는) 과정을,
  ㅇ 전체 자료에서 하나씩 진행하며 반복적으로 수행


2. 선택 정렬 특징

  ㅇ 입력 배열 외에 추가적인 메모리가 불필요 
     - 제자리 정렬 (in-place sorting)

  ㅇ 기본 연산 둘 : 비교 연산, 교환 연산

  ㅇ 비교 필요 횟수 : 총 n(n-1)/2회의 데이터 비교가 필요함
     - 설사 정렬되어 있더라도, 총 n(n-1)/2회의 데이터 비교가 필요함

  ㅇ 시간복잡도 : O(n2)
     - 데이터량이 적을때는 좋은 성능을 보임


3. 선택 정렬 방법

  ㅇ 2개의 중첩 루프를 사용
     - 외부 루프배열의 첫 요소부터 마지막까지 반복
     - 내부 루프배열의 다음(나머지 첫) 요소부터 마지막까지 반복

  ㅇ 즉, 
     - 처음과 나머지 자료들과 비교하면서, 
     - 제일 큰/작은 자료를 맨 왼쪽에 두도록, 위치 교환
     - 다음과 그 나머지 자료들과 비교,위치 교환을 반복해가며 정렬해나감


4. 프로그래밍 例 (C 언어)

    
/* 선택정렬 (오름차순) */
Input  : (정렬 전 데이터 배열) Data[], (배열 데이터 수) int n
Output : (정렬 후 데이터 배열) Data[]

void SelectionSort(int Data[], int n) {
    int outer, inner, min;
    for (outer = 0; outer < n-1; outer++) {
        min = outer;
        for (inner = outer + 1; inner < n; inner++) {
            if (Data[inner] < Data[min]) {
               min = inner;
            }
        }
        swap(&Data[outer],&Data[min]);
    }
}


[정렬 알고리즘] 1. 정렬 알고리즘 2. 버블 정렬 3. 선택 정렬 4. 삽입 정렬

 
        최근수정     요약목록     참고문헌