[알고리즘] 선택정렬 (Selection Sort) 정리 및 예제

 

| 문제

배열을 작은 정수에서 큰 정수 순서로 정렬하는 코드입니다.

 

| 해결 방법

1. findSmallest(): 배열에서 가장 작은 원소를 찾는 함수를 구현한다. (여기서 정렬하지 않는다.)

2. selectionSort(): 새 배열에 가장 작은 원소를 추가하는 정렬 함수를 구현한다. (여기서 정렬을 한다.)

 

주의할 점

findSmallest() 메소드

for i in range(1, len(arr)):

범위 1~ (arr크기-1)

(1)range()의 매개변수에는 정수 타입만 올 수 있다. 

-range(arr) 타입이 맞지 않아 TypeError발생 

-TypeError: 'list' object cannot be interpreted as an integer

 

(2)(1, len(arr))에서 1로 시작하는 이유

-이미 for문 전에 가장 작은 원소의 인덱스와 값을 저장할 변수를 선언했다. 

-0부터 시작해 첫번째 원소끼리 값 비교하는 것은 무의미하다. 자원 낭비.

---

 

selectionSort()메소드

for i in range(len(arr)):

1.range(len(arr))에서 인덱스 0부터 시작하는 이유

-값 비교가 아닌 가장 작은 정수 값을 추가하여 새로운 리스트 생성을 하기 때문

 

newArr.append(arr.pop(smallest_index))

2.pop()

(1) 사용 이유

-선택 정렬은 실행할 때마다 더 적은 항목을 점검한다. O(n^2)

-연산을 할 때 실제로 점검해야 할 항목의 수는 줄어든다. 최종적으로 하나의 항목만 남는다. 

-pop을 쓰지 않으면 가장 적은 수를 찾는 메소드(findSmallest()) 실행 결과가 동일하다.

 

(2) 형식

pop(idx, val) 

return값: val

val을 리턴하고 해당 배열에서 val을 삭제

 

| 궁금한 점

1.findSmallest() > for > 'smallest = arr[i]' 가 필요할까?

주석처리 후 실행결과는 이상 없다. 

Q: 그럼에도 있어야할 이유는? 

 

2.range()대신 enumerate()로 대체해도 되는가?

여기서 인덱스와 값을 쌍으로 이용하는 경우가 없으니 굳이 필요없다.

 

 

 

#문제: 배열을 작은 정수에서 큰 정수 순서로 정렬하는 코드
 
#작은 수 찾기. 순서 바꾸지 않음
def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
 
    #작은 수 탐색
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index
 
 
#선택 정렬. 새로운 배열에 가장 작은 수를 차례대로 추가
def selectionSort(arr):
    newArr = []
    #for문이 없으면 selctionSort 10번을 호출해야 새로운 리스트가 완성된다.
    #for문 사용 필수.
    for i in range(len(arr)):
        #range(1, len(arr)) -> 기존 arr의 원소중 1개의 원소가 newArr에 추가되지 않음. [1, 4, 6, 7]
        #range(len(arr)) -> [1, 4, 6, 7, 9]
        smallest_index = findSmallest(arr)
        #pop(idx, val) return val 배열에서 idx에 해당하는 val 리턴 후 배열에서 삭제
        newArr.append(arr.pop(smallest_index))
 
    return newArr
 
 
arr = [4,6,1,7,9]
print(selectionSort(arr))

 

|참고

 

Hello Coding 그림으로 이해하는 알고리즘 책의 소스코드와 제가 정리한 내용으로 구성되었습니다 

소스코드는 다음 깃허브 페이지 및 출판사 제공 소스코드를 참고하였습니다.

https://github.com/egonSchiele/grokking_algorithms/blob/master/02_selection_sort/python/01_selection_sort.py

GitHub - egonSchiele/grokking_algorithms: Code for the book Grokking Algorithms (https://amzn.to/29rVyHf)

 

알고리즘을 처음 공부하는 중입니다. 오류, 조언, 지적할 것이 있다면 환영하니, 꼭 댓글 부탁드립니다.