[Algorithm] 선택 정렬 - Selection Sort (Python)

📌 선택 정렬

선택 정렬은 현재 인덱스에 들어갈 값을 선택하여 정렬하는 알고리즘이다.

추가 메모리를 사용하지 않기 때문에 In-place 정렬이지만, 동일한 값들의 순서가 변할 수 있기 때문에 Unstable 정렬이다.

아이디어

1. 배열의 가장 마지막 인덱스를 선택한다.
2. 현재 인덱스 이전의 값들을 비교하여 가장 큰 수를 선택한다.
3. 선택된 두 값을 교체한다.
4. 인덱스를 줄여가며 위의 과정을 반복한다.

복잡도 분석

• 선택 정렬은 추가적인 공간을 사용하지 않고 주어진 배열 내에서 값들의 위치만 바뀌기 때문에 O(1)의 공간 복잡도를 갖는다.
  
  
• 루프문을 통해 배열의 모든 값에 접근해야 하기 때문에 기본적으로 O(N)의 시간을 소모한다. 이때, 각 루프마다 현재 인덱스를 제외한 값들 중 최대값을 찾고, 이를 현재 인덱스의 값과 교환(swap)해주어야 하기 때문에 O(N)의 시간을 필요로 한다. 따라서 선택 정렬은 O(N^2)의 시간 복잡도를 갖는다.
  
  

특징

👍 장점

• 구현이 간단하다.
• 데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다.
• 비교 횟수에 비해 교환 횟수가 적다.

👎 단점

• 시간이 오래 걸린다.
• 정렬된 상태에서 데이터가 추가되었을 때 정렬 효율이 좋지 않다.

구현

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

n = len(arr)

for i in range(n-1, 0, -1):
	max_idx = i

	for j in range(i):
		if arr[j] > arr[max_idx]:
			max_idx = j
	
	arr[i], arr[max_idx] = arr[max_idx], arr[i]

--

참고 사이트

🙇🏻‍♂️ https://jbhs7014.tistory.com/180