티스토리 뷰

반응형

  • 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.


  선택 정렬(Selection Sort)은  정렬되지 않은 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식이다. 선택 정렬을 사용하여 특정 배열의 값을 오름차순으로 정렬하기 위한 다음과 같은 코드를 생각할 수 있다.

void SelectionSort(int arr[]int MAX) {
    int i, j;
    int min, temp;
    for(i=0; i<MAX-1; i++) {
        min = i;
        for(j=i+1; j<MAX; j++) {
            if(arr[j] < arr[min]) min = j;
        }
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}


  SelectionSort 함수의 인자 arr은 정렬되지 않은 배열이고 MAX는 배열의 개수가 들어온다. 함수는 처음에 min에 i의 값을 넣는다. 그리고 두번째 for문이 돌아가면서 arr[min] 보다 작은 값을 발견하면 min의 값을 j로 바꾼다. 그리고 j 변수로 돌아가는 for문이 완료 되었을 때 arr[i]와 arr[min]의 값을 교환한다. 쉽게 구현할 수 있는 만큼 프로그래밍시 개인적으로 자주 사용하는 정렬 기법이다. 

  자료구조를 처음배우거나, 알고리즘이 익숙하지 않으면(나같으면) 충분히 머리 아플 수 있다.. 그래서 동영상을 하나 준비했다. 루마니아 사피엔티아 대학교에서 촬영한 'Select-sort with Gypsy folk dance'. 선택 정렬을 집시 포크 댄스로 표현했다. 동영상을 보고나면 선택 정렬이 어떤 놈인지 대충 감이 잡힌다.


  선택 정렬에서 두개의 반복문(위의 소스에서 for문)이 돌면서 시행되는 연산의 횟수는 다음과 같다. 

(MAX는 배열의 개수) 

(이렇게 표현하기도 한다.) 


  선택정렬은 비교 연산 및 이동 연산 횟수가 고정된 값(MAX의 제곱)이므로 최악의 연산 횟수의 경우나 평균 연산 횟수 값이나 정렬의 효율성은 MAX의 제곱이 된다. (사실 두개의 반복문이 종료된 후 반드시 교환 연산이 이루어지므로 최선, 최악의 의미가 없다.) 전체적인 알고리즘 효율성을 볼 때 느리다는 점과, 안정성을 만족하지 않는다(같은 값의 인덱스끼리도 교환 연산이 발생 가능)는 단점이 있다.


참고 도서


자료구조

저자
이상진 지음
출판사
프리렉 | 2010-01-15 출간
카테고리
컴퓨터/IT
책소개
열혈강의 자료구조 출판사 서평자료구조에 대한 지식을 쌓고 관련 ...
가격비교


반응형
프로필사진

Yowu (Yu Yongwoo)

흔한 Node.js/Java 백엔드 개발자입니다
Ubuntu와 MacOS 데스크탑 개발 환경을 선호합니다
최근에는 vscode와 IntelliJ를 사용하고 있습니다
vscode에는 neovim, IntelliJ는 ideaVim
개발용 키보드는 역시 HHKB Pro 2 무각입니다
락 밴드에서 드럼을 쳤습니다

  • 프로필사진 지나가다 영상이 재밌네요!! 그런데 영상의 내용은 선택정렬이라기보다 버블정렬 같은데, 아닌가요?? 2015.09.30 21:51
  • 프로필사진 부니 잘봤습니다. 직접 알고리즘 해보니 괄호가 잘 눈에 안띄더군요

    알고리즘이 맞긴 합니다.

    영상도 바로 옆에 있는것과 비교가 아니라, 가장 작은 값을 찾은 후 자리를 바꾸는 게 sort selelction이니 영상이 조금 맞지 않는다는 생각이 들긴 합니다.

    정말 도움 많이 되었습니다.

    감사합니다.^^
    2015.10.04 09:44
  • 프로필사진 안녕하세요 동영상이.. 인서션소트 아닌가요?ㅠㅠ 2016.01.05 00:16
댓글쓰기 폼