선택 정렬

정의

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

 

동작 과정

• 주어진 배열 중에 최소값을 찾는다.

• 그 값을 맨 앞에 위치한 값과 교체한다.

• 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

 

Python 코드

def selectionSort(x):
	length = len(x)
	for i in range(length-1):
	    indexMin = i
		for j in range(i+1, length):
			if x[indexMin] > x[j]:
				indexMin = j
		x[i], x[indexMin] = x[indexMin], x[i]
	return x

 

Java 코드

void selectionSort(int[] list) {
    int indexMin, temp;
    for (int i = 0; i < list.length - 1; i++) { // 1.
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) { // 2.
            if (list[j] < list[indexMin]) { // 3.
                indexMin = j;
            }
        }
        temp = list[indexMin];  // 4.
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

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

동작 방식(GIF)

 

 

시간 복잡도

• 첫 번째 회전에서 비교 횟수 n-1, 두 번째 회전에서 비교횟수 n-2 ….

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

• n개의 주어진 배열을 정렬하는데 O(n²)만큼 시간이 걸린다.

• 최선, 최악, 평균의 경우 시간복잡도가 O(n²)로 동일하다.

공간 복잡도

• 별도의 추가 공간을 사용하지 않고 주어진 배열 안에서만 교환하므로 O(1)이다.

 

장점

• 거품 정렬(Bubble Sort)과 마찬가지로 알고리즘이 단순하다.

• 거품 정렬(Bubble Sort)에 비해 실제로 교환하는 횟수가 적기에 비교적 효율적이다.

• 거품 정렬(Bubble Sort)와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식으로, 다른 메모리 공간이 필요하지 않다(제자리 정렬)

• 배열이 작을 때 효율적이다.

단점

• 시간복잡도가 O(n²)로 비효율적이다.

• 불안정 정렬이다(중복된 값이 입력 순서와 동잃지 않게 정렬되는 알고리즘)

 

개선 방법

• 이중 선택 정렬 : 한 번의 탐색에서 최솟값과 최댓값을 같이 찾는 방법, 탐색 횟수가 절반으로 줄어든다.