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

Goal

• 선택 정렬에 대해 설명할 수 있다.
• 선택 정렬 과정에 대해 설명할 수 있다.
• 선택 정렬을 구현할 수 있다.
• 선택 정렬의 시간복잡도와 공간복잡도를 계산할 수 있다.

Abstract

선택 정렬은 버블 정렬과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.

선택 정렬은 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하자!

Process

1. 주어진 배열에서 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

Code

void selectionSort(int[] arr) {
	int indexMin = 0;
	int temp = 0;
    for(int i = 0; i < arr.length-1; i++) {        // 1
    	indexMin = i;
    	for(int j = i + 1; j < arr.length; j++) { // 2
        	if(arr[j] < arr[indexMin]) {          // 3
            	indexMin = j;
            }
        }
        temp = arr[indexMin];                     // 4
        arr[indexMin] = arr[i];
        arr[i] = temp;
    }
    System.out.println(Arrays.toString(arr));
}

1. 위치(index)를 선택해준다.
2. i+1번째 원소부터 선택한 위치의 값과 비교를 시작한다.
3. 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치를 갱신해준다.
4. 2번 반복문이 끝난 후 indexMin에 1번자리에 들어가야 할 값의 위치를 갖고 있으므로 서로 교환한다.

시간복잡도

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2)만큼 시간이 걸린다. 따라서 최선, 평균, 최악의 경우 시간복잡도는 O(n^2)로 동일하다.

공간복잡도

주어진 배열 안에서 교환을 통해, 정렬이 수행되므로 O(n)이다.

장점

• 정렬을 위한 비교 횟수는 많지만, 버블 정렬에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나는 자료상태에서 효율적이다.
• 버블 정렬과 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬

단점

• 시간 복잡도가 최악, 최선, 평균 모두 O(n^2)으로 비효율적이다.
• 불안정 정렬이다.