[자료구조] 선택 정렬(Selection sort) -Python

파이썬 자료구조와 알고리즘 - 한빛아카데미

 

파이썬 자료구조와 알고리즘 교재 공부한 내용을 적어보았습니다.

---

선택 정렬(Selection sort)이란 여러 데이터 중 가장 작은 값을 뽑는 동작을 반복하여 값을 정렬하는 방식입니다.

 

이 선택정렬을 구현하려면 데이터 중 가장 작은 값을 알아내야 합니다.

---

 

선택 정렬 1

def findMinIdx(array):
	minIdx = 0
    for i in range(1, len(array)):
    	if array[minIdx]>array[i]:
        	minIdx = i
    return minIdx

위 코드는 최솟값의 index를 찾는 findMinIdx 함수를 구현한 것입니다.

 

1. 정렬되지 않은 array에서 0번 index를 minIdx 즉, 최솟값의 index로 지정합니다.

2. for문을 순회하며 array에서 array [minIdx]보다 작은 값이 있으면 그 값의 index를 minIdx로 지정합니다.

3. for문의 순회가 끝나면 minIdx는 array에서 최솟값의 index가 됩니다.

4. minIdx를 반환합니다.

 

array를 다음과 같이 설정해서 예시를 들어보겠습니다.

array = [5, 3, 4, 1, 2]

 

1. 초기 minIdx = 0입니다. (array [0] = 5입니다.)

2. i = 1일 때 array [0] > array [1] → 5>3 이기 때문에 minIdx = 1이 됩니다.

3. i = 2일 때 array [1] < array [2] → 3 <4 이기 때문에 minIdx는 여전히 1입니다.

4. i = 3일 때 array [1] > array [3] → 3>1 이기 때문에 minIdx = 3이 됩니다.

5. i = 4일 때 array [3] < array [4] → 1 <2 이기 때문에 minIdx는 여전히 3입니다.

for문 순회를 완료한 후 array에서 최솟값인 1의 index가 minIdx가 되어 3이 반환됩니다.

 

def findMinIdx(array):
	minIdx = 0
    for i in range(1, len(array)):
    	if array[minIdx]>array[i]:
        	minIdx = i
    return minIdx

before = [188, 162, 168, 120, 50, 150, 177, 105]
after = []

print('정렬 전 -->', before)
for _ in range(len(before)):
	minPos = findMinIdx(before)
    after.append(before[minPos])
    del(before[minPos])
print('정렬 후 -->', after)

위 코드는 findMinIdx 함수를 사용하여 선택 정렬을 실시하는 코드입니다.

1. for문을 before의 길이만큼 순회하며 before의 작은 값부터 after에 append 합니다.

2. append 된 값은 before에서 삭제합니다.

3. after에 정렬이 완료됩니다.

 

---

선택 정렬 2

 

선택 정렬 1에서는 배열이 2개 필요했습니다.

선택 정렬 2에서는 더 효율적으로 한 개의 배열로 처리해보겠습니다.

def selectionSort(array):
	n = len(array)
    for i in range(0, n-1):
    	minIdx = i
        for j in range(i+1, n):
        	if array[minIdx] > array[j]:
                minIdx = j
        array[i], array[minIdx] = array[minIdx], array[i]
    return array        

위 코드는 한개의 배열에서 선택 정렬을 처리한 코드입니다.

첫 번째 for문의 순회를 사이클이라고 하겠습니다. (i = 0 일 때 사이클1, i = n-2 일때 사이클 n-1)

1. 사이클 1에서 0번째 index를 minIdx로 설정합니다.

2. 두 번째 for문을 순회하며 0번째 index의 값보다 작은 값의 index를 minIdx로 지정합니다.

3. array [i]와 array [minIdx] 값을 서로 교환합니다.

 

이 사이클을 반복하면 배열은 오름차순으로 정렬이 됩니다.

 

---

선택 정렬의 알고리즘 성능은 이중 for문이 사용되기 때문에 $O(n^2)$입니다.

좋은 알고리즘이라고 할 수는 없을 것  같습니다.