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

정렬 알고리즘은 2가지 방법으로 나뉘어진다.

• 단순하지만 비효율적인 방법 : 선택 정렬, 삽입 정렬, 버블 정렬
• 복잡하지만 조금 더 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

선택 정렬

• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘.
• 현재 위치에 저장될 값의 크기가 작은지, 큰지에 따라 최소 선택 정렬(오른차순 정렬)과 최대 선택 정렬(내림차순 정렬)로 나뉜다.

로직

1. 주어진 배열에서 첫번째 인덱스를 기준으로 잡는다. 기준은 처음부터 시작한다.
2. 주어진 배열에서 기준 이후의 값 중 최소값을 찾는다.
3. 최소값과 그 기준의 값을 교체한다.
4. 기준 이후 나머지 배열을 같은 방법으로 교체한다.

int[] arr = {7,6,2,4,3,9,1}

private static void sort(int[] arr){
	for(int i=0; i<arr.length; i++){
	    	int standard = i;
		for(int j = i+1; j<arr.length; j++{
			if(arr[j] <arr[standard]) standard = j;
		}
    
                //자리 바꾸는 과정
                int temp = arr[standard];
                arr[standard] = arr[i];
                arr[i] = temp;

                print(arr);
    	}
}

private static void print(int[] arr){
	for(int i=0; i<arr.length; i++){
    	System.out.println(arr[i]+" ");
    }
    System.out.println();
}

// 단계별 결과.
1단계 : 1 6 2 4 3 9 7 
2단계 : 1 2 6 4 3 9 7 
3단계 : 1 2 3 4 6 9 7 
4단계 : 1 2 3 4 6 9 7 
5단계 : 1 2 3 4 6 9 7 
6단계 : 1 2 3 4 6 7 9 
7단계 : 1 2 3 4 6 7 9

• 위치(index)를 선택. (주로 배열의 첫 번째 부터 시작한다.)
• i+1번째 원소부터 선택한 위치 값과 비교를 시작.
• 오름차순이므로 현재 선택한 자리에 있는 기준 값보다 순회하고 있는 값이 작다면 위치를 갱신해준다.
• 코드의 2번 반복문이 끝난 뒤엔 작은 값을 찾아 갱신했음으로 처음에 선택했던 기준값과 작은 값의 위치를 서로 교환해준다.

"기준이 되는 수와 나머지 수를 비교해서 가장 작은 수를 앞으로 계속 보내는 정렬"

간단하지만, 매우 비효율적.
1단계 -> N개의 원소 비교
2단계 -> N-1개의 원소 비교
...
비교 횟수 = n(n-1)/2가 된다.

시간 복잡도는 O(N^2)가 된다.
최악, 최선, 평균 모두 시간 복잡도가 O(N^2)가 된다.
공간 복잡도는 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.

장점

• 알고리즘이 단순하다.
• 정렬을 위한 비교는 여러번 수행되지만, 실제로 교환 횟수는 적기에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적인 면이 있다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이기에 다른 메모리 낭비는 안한다.

단점

• 시간복잡도가 O(N^2)로 매우 비효율적이다.
• 불안정 정렬이다.

Reference

• Ready-For-Tech-Interview