Selection Sort (선택 정렬)

Selection Sort (선택 정렬)

• 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환
  
• 해당 index 위치에 넣을 값을 "선택"하는 알고리즘
• 주어진 배열에서 최소값을 찾아 해당 자리에 맞도록 교체
• 거품정렬과 다르게 N번 스왑하지 않음
• 다시말하면, 거품 정렬은 계속 스왑해줘야해서 실행속도가 매우 느린 반면 선택정렬은 그 정도는 아니다

[선택 정렬 과정]

	1. 앞에서부터 데이터 하나를 선택한다.
    2. 내가 선택한 데이터 이후에 있는 우너소들 중 가장 작은 값을 찾는다.
    3. 내가 선택한 값과 바꾼다.

[ 시간복잡도 ]

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

• 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) ▶︎ n-1
• 두 번째 회전에서의 비교횟수 : 2 ~ (n-2) ▶︎ n-2
  ...
• (n-1) + (n-2) + ... + 2 + 1 ▶︎ n(n-1)/2

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

[ 최종 정리 ]

1. 제일 작은 숫자를 찾기 위해 순차적으로 이동

2. Outer 루프가 한번 돌때마다 element 하나의 최종 위치가 확정

3. 탐색 범위
	- Outer : 0 -> n-1
			첫번째 element를 가장 낮은 숫자로 가정
	
    - Inner : 0 -> i+1
			이미 정렬된 부분을 제외
			가장 낮은 숫자(i) 다음 인덱스부터 비교

4. Time Complexity
	- worst   : O(n^2)
	- Average : O(n^2)
	- Best    : O(n^2) 

[ 코드 ]

def selectionSort(arr):
    n = len(arr)

    for i in range(n-1):
        min = i
        for j in range(i+1, n):
            if arr[min] > arr[j]:
                min = j
        arr[i], arr[min] = arr[min], arr[i]

arr = [-2, 45, 0, 11, -9,88,-97,-202,747]

selectionSort(arr)
print(arr)