[알고리즘] 파이썬으로 선택정렬 (Selection Sort) 구현하기

정렬 알고리즘 중 하나인 선택정렬(selection sort)은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 알고리즘이다. 알고리즘에 대한 공부를 위해 적절한 강의를 찾았는데, 기본적으로 제공되는 내용은 C를 기반으로 하기 때문에 이를 Python으로 바꿔서 해보려고 한다.

 

(모든 내용은 아래 참고의 블로그 및 유튜브를 참조)

---

선택정렬을 하기 위해서 실행하는 알고리즘의 순서는 다음과 같다.

 

1. 주어진 배열을 하나씩 탐색한다.

2. 탐색 지점부터 배열의 끝까지 값 중 가장 작은 값을 찾는다.

3. 그 작은 값을 탐색 지점에 놓고, 탐색 지점의 값을 가장 작은 값이 있던 곳에 놓는다. (데이터 교환, 스와핑)

 

그 전체 알고리즘은 아래와 같다.

array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]

# 가장 작은 것을 선택해 제일 앞으로 보내기
def selection_sort(array):
    for i in range(len(array)):
        bound = 9999  # 비교를 위해서 데이터의 어떤 값보다 큰 숫자
        # 가장 작은 것을 찾고, 그 위치를 ind에 저장
        for j in range(i, len(array)):
            if (bound > array[j]):
                bound = array[j]
                ind = j
        # 스와핑 
        temp = array[i]
        array[i] = array[ind]
        array[ind] = temp
    print(array)

selection_sort(array)

 

결과는 잘 나오는 것으로 볼 수 있다. 다만, 이 알고리즘이 어떻게 동작하는지 보려면 함수 맨 마지막에 있는 print 함수를 들여쓰기해서 아래 코드 처럼 쓰면, 어떻게 동작하는지 잘 볼 수 있을 것이다. 

 

array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]

# 가장 작은 것을 선택해 제일 앞으로 보내기
def selection_sort(array):
    for i in range(len(array)):
        bound = 9999  # 비교를 위해서 데이터의 어떤 값보다 큰 숫자
        # 가장 작은 것을 찾고, 그 위치를 ind에 저장
        for j in range(i, len(array)):
            if (bound > array[j]):
                bound = array[j]
                ind = j
        # 스와핑 
        temp = array[i]
        array[i] = array[ind]
        array[ind] = temp
    	print(array)

selection_sort(array)

 

참고:

- 안경잡이개발자, "2. 정렬의 개요와 선택정렬(Selection Sort)", https://blog.naver.com/ndb796/221226800661

2. 정렬의 개요와 선택 정렬(Selection Sort)