[Sort] 선택정렬 (Select Sort)

선택정렬 (Select Sort)

선택정렬에 알아보겠습니다. 선택정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾고, 정렬 대상 요소와 교환하는 방식이다. 

간단히 제일 작은 요소부터 앞에서 부터 차례대로 줄을 서는 것이다.

그림으로 설명해보자.

3회전을 하는 과정이다.

우선 회색으로 칠해져 있는 것은 아직 정렬되지 않은 영역이다.

정렬되지 않은 영역 첫번째 부터 차근차근 정렬을 하면 된다. 정렬되지 않은 요소 중 첫번째 요소인 5와 나머지 요소를 비교하여 가장 작은 요소의 index 위치를 찾는다. 

찾은 후 교환해주면 된다. 

위 원리를 코드로 나타내면 다음과 같다. 

package Sort;

import java.util.Arrays;

public class SelectSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array = {5,3,4,7,6,2,1};
		System.out.println("Before   : "+Arrays.toString(array)+"\n");
		selectSort(array);

	}
	
	//시간복잡도 n-1,n-2,n-3...1 -> O(n^2)
	//공간복잡도 하나의 배열에서만 진행 O(n)
	private static void selectSort(int[] array) {
		int temp = 0;
		int index = 0;
		for(int i=0; i<array.length-1; i++){
			index = i;
			for(int j=i+1; j<array.length; j++){
				if(array[index] > array[j]){
					index = j;
				}
			}
			 temp = array[i];
			 array[i] = array[index];
			 array[index] = temp;
			
			 System.out.println((i+1)+"번째 select sort result : " + Arrays.toString(array));	
		}
	
	}
		
		
	}


	

선택정렬의 장점은 데이터량이 적을 때 좋은 성능을 나타낸다. 또 작은 값을 선택하기 위해 비교는 많이 하지만, 교환은 한번만 이루어 진다는 것이 장점이다.

단점은 100개 이상의 자료에서는 속도가 급격히 떨어진다. 

시간의 복잡도는 n-1,n-2,n-3 .... 1 -> O(n^2)

공간의 복잡도는 하나의 배열에서만 진행되기 때문에 O(n)