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. 삽입 정렬
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램,프로그래밍
      1.   프로그래밍 언어론
      2.   구조적 프로그래밍
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 알고리즘 설계
            3. 계산 복잡도
            4. 하노이 탑
            5. 순서도
            6. 재귀 호출
        1.   알고리즘 종류
              1. 알고리즘 분류
              2. 그래프 알고리즘
              3. 최대 최소 구하기
              4. 유클리드 알고리즘
          1.   정렬 알고리즘
            1.   1. 정렬 알고리즘
                2. 버블 정렬
                3. 선택 정렬
                4. 삽입 정렬
          2.   검색 알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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