선택 정렬(selection sort)

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

wiki의 설명을 바탕으로 적어보았습니다.
여기서 제자리 정렬이란 같은 값이 있을때 정렬을 할 경우 data의 순서가 입력 그대로 존재한다는 의미입니다.

예제

아래 예제에서 최솟값은 굵게 되어있는 숫자 중에서 결정을 합니다. 진하지 않은 글자는 이미 정렬된 상태를 의미합니다.
pass마다 남은 숫자들중에 최소값을 하나씩 찾아서 오른쪽부터 기록을 해 둡니다. 기록은 swap으로 값을 교환하는 방식으로 합니다.
wiki에 자세히 설명이 되어있기 때문에 내용을 크게 정리하지 않아도 될 듯 하네요.

패스	테이블	최솟값
0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8

의사코드

SelectionSort(x)
{
  for i:0->N-1
  {
    index=GetMinIndex(i,N-1)
    swap(i,index)
  }
}

GetMinIndex(int idxstart,int idxend)
{
  idx = idxstart, min = data[idxstart]
  for i:idxstart+1->idxend
  {
    if( min > data[i] ){
       min = data[i], idx = i
    }
  }
  return idx
}


예제나 만들어 보겠습니다.

C, pasted just now: 

#include <stdio.h> int data[]={9,1,6,8,4,3,2,0}; int N = 8; int GetMinIndex(int idxstart,int idxend) { int i; int idx = idxstart, min = data[idxstart]; for(i=idxstart+1;i<idxend;i++) { if( min > data[i] ){ min = data[i], idx = i; } } return idx; } int swap(int i,int j) { int temp; if(i==j) return 0; temp=data[j]; data[j]=data[i]; data[i]=temp; } int SelectionSort() { int i; int index; for(i=0;i<N;i++) { index=GetMinIndex(i,N); swap(i,index); } } int main() { int i; SelectionSort(); for(i=0;i<N;i++){ printf("%d",data[i]); } return 0; }

Output:

01234689