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

Selection Sort란?

• BubbleSort와 유사한 알고리즘으로 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘 
• 원소 중 가장 작은  값을 선택하여 앞으로 이동  
• 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬
• BubbleSort에 비해 교환 횟수가 적기 때문에 많은 교환이 일어나는 자료상태에서는 비교적 효율적이다.
• 불안정 정렬이다.

Selection Sort 과정

1. 배열에서 최소값을 찾는다.
2. 찾은 값을 맨 앞의 원소와 비교한 후 교체
3. 맨 앞의 원소를 제외하고 1-2 반복   

선택정렬 과정

Selection Sort Code

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

 

시간복잡도

• (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 

최선	평균	최악
O(n^2)	O(n^2)	O(n^2)

 

[참고 자료]

• 링크