손가락놀이터

이 글은 gyoogle님의 github에 있는 자료를 바탕으로 작성되었습니다.

Abstract

Selection Sort는 Bubble Sort와 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

Selection Sort와 Insertion Sort를 헷갈려하시는 분들이 종종 있는데, Selection Sort는 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하시면 편합니다.

Process

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

Python Code

def selectionSort(arr:list):
	for i in range(len(arr)):			# 1.
		minimum_val, minimum_idx = 0, 0
		for j in range(i+1, len(arr)):		# 2.
        	
			if minimum_val > arr[j]:		# 3.
				minimum_val = arr[j]
				minimum_idx = j
		arr[i], arr[minimum_idx] = arr[minimum_idx], arr[i]		# 4.
    
    
    return arr

1.  우선, 위치(idx)를 선택합니다.
2. 선택한 위치의 값과 i+1번째 원소부터 차례대로 비교를 시작합니다.
3. 오름차순으로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(idx)를 갱신합니다.
4. [2]번 반복문이 끝난 뒤에 선택한 위치의 값과 기존 가장 작은 값을 서로 교환(swap)해줍니다.

시간 복잡도

데이터의 개수가 n개라고 했을 때,

• 첫 번째 회전에서의 비교횟수 : 1~(n-1) -> n-1
• 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) -> n-2

최종적으로 $(n-1)+(n-2)+....+2+1 \rightarrow n(n-1)/2$

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

위의 코드를 통해 자세히 계산해보면 아래와 같습니다.

1. n번 반복
2. n-1, n-2, ...., 2, 1번 반복
3. if문 및 이하는 1번 실행
4. swap 부분 1번 실행
5. 식으로 표현하면 $\Sigma \Sigma (O(1)+O(1)+O(1)) + O(1)$ 입니다.
6. 따라서 시간복잡도는 $O(n^2)$ 입니다.

공간 복잡도

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

장점 & 단점

1. 장점
   • Bubble sort와 마찬가지로 알고리즘이 단순하다.
   • 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야하는 자료 상태에서 비교적 효율적입니다.
   • Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. -> 제자리 정렬(in-place sorting)
2. 단점
   • 시간 복잡도가 $O(n^2)$로 비효율적입니다.
   • 불안정 정렬(Unstable Sort)입니다.

추가적인 왜?

Unstable Sort가 정확히 무엇이지?

1. Stable Sort(안정 정렬)
   • 비교 대상의 Key가 여러개 값을 가질 때 혹은 같은 값을 가지는 데이터가 여러개가 있을 때, 정렬 후에 기존의 순서를 유지하는 정렬.
   • 즉, 정렬되지 않은 상태에서 같은 키 값을 가진 원소의 순서가 정렬 후에도 유지되느냐 이다.
   • Bubble Sort, Insertion Sort, Merge Sort, Counting Sort, Bucket Sort, Radix Sort
2. Unstable Sort(불안정 정렬)
   • 비교 대상의 Key가 여러개 값을 가질 때 혹은 같은 값을 가지는 데이터가 여러개가 있을 떄, 정렬 후에 기존의 순서가 유지 되지 않는 정렬
   • 예를 들어서 다음 5 3 1' 9 2 1이 있다면 1 1' 2 3 5 9 와 1' 1 2 3 5 9가 나올 수 있다.
   • Selection Sort
   • Shell Sort
   • Heap Sort
   • Quick Sort