[알고리즘] 기초 정렬 알고리즘 - 선택 정렬(Selection Sort)

 

선택 정렬

잘못된 위치에 들어가 있는 원소를 찾아

그것을 올바른 위치로 옮겨 주는 원소 교환(exchange) 사용하여 정렬 수행

 

작은 키와 매우 큰 레코드를 가지는 화일을 정렬하는데 적합

실행시간은 입력자료순서에 민감하지 않음

제자리 정렬

불안정적인 알고리즘

 

N개의 원소일때,

비교 N-1번 / 교환 0번 ~ 1번

한번 정렬을 하고 난 후,

비교 N-2번 / 교환 0번 ~ 1번

두번 정렬을 하고 난 후

비교 N-3번 / 교환 0번 ~ 1번

..

..

..

전체 비교 횟수 N(N-1)/2 => 시간복잡도 O(N^2)

 

선택정렬 알고리즘을 C++로 구현한 경우

void SelectionSort(int a[], int n)  {      int i, j, min;      for ( i = 1; i < n; i++) {         min = i;         for ( j = i+1; j <= n; j++)            if ( a[j] < a[min]) min = j;         swap(a, min, i);      }  }    void swap(int a[], int i, int j)  {      int t = a[i];     a[i] = a[j];     a[j] = t;  }

 

선택 정렬 알고리즘

SelectionSort(a[], n)  {      for ( i <- 1; i < n; i < i+1) do {         배열 [a], ....... , a[n] 중에서 가장 작은 원소 a[k]를 선택;         a[k]를 a[i]와 교환;      }  }