Selection Sort   선택 정렬

(2019-01-08)
1. 선택 정렬 (Selection Sort)

  ㅇ 가장 큰/가장 작은 자료를 선택하고(찾고) 선두로 옮기는(교환하는) 과정을 반복적으로 수행

  ㅇ 정렬 방법
     - 중첩 루프를 사용
        . 외부 루프배열의 첫 요소부터 마지막까지 반복
        . 내부 루프배열의 다음(나머지 첫) 요소부터 마지막까지 반복
     - 즉, 
        . 처음과 나머지 자료들과 비교하면서, 제일 큰/작은 자료를 맨 왼쪽에 두며, 위치 교환
        . 다음과 나머지 자료들과 비교,위치 교환을 반복해가며 정렬해나감

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

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

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

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


2. 프로그래밍

  
/* 선택정렬 (오름차순) */
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. 삽입 정렬

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