728x90
선택 정렬은 0번 인덱스를 마지막번 인덱스까지 차례대로 비교해 가장 작은 값을 찾아 0번에 놓고, 1번 인덱스를 차례대로 비교해 그 중 가장 작은 값을 찾아 1번에 놓는 과정을 반복하며 정렬을 수행한다. 1회전을 수행하고 나면 최소값이 맨 앞에 오게 되므로 2회전에서는 맨 앞인 0번 인덱스를 빼고 정렬을 진행하면 된다.
선택 정렬의 성능 분석 공식은 T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)로 버블정렬과 동일하다.
5 3 1 4 2를 가지고 선택 정렬을 수행하는 과정은 위의 이미지와 같다. 최소값을 담아둘 임의의 변수 min값이 필요함을 알 수 있다. 자바로 작성하면 다음과 같다.
public class Selection {
public static void selection(int[] a){
int N = a.length;
int min; //최소값의 인덱스를 저장할 변수
for(int i=0; i<N-1; i++){
min = i;//j번째 인덱스랑 비교하기 위한 초기화
for(int j=i+1; j<N; j++){
if(a[min] > a[j])
min = j;//최소값의 인덱스를 min에 저장
}
int temp = a[min];
a[min] = a[i];
a[i] = temp;//swap
}
}
public static void main(String[] args) {
int[] a= {8,31,48,73,3,65,20,29,11,15};
selection(a);
for(int i:a){
System.out.printf("%d ",i);
}
}
}
지난 버블 정렬과 동일하게 10000개의 데이터를 정렬하는데 걸린 시간을 측정해보았다.
같은 IDE에서 같은 데이터 양으로 비교했는데 실행시간은 약 2초 이상이 차이났다. (버블 정렬은 2.654였음). 버블 정렬에 비해서는 선택 정렬이 더 빠름을 알 수 있다.
728x90
