기본 정렬3. 선택 정렬(Selection Sort) 구현하기

1. 선택 정렬(Selection Sort)의 기본 개념

2. 선택 정렬의 예시와 원리 파악

3. 실제 코드 구현 및 예시를 통한 이해 

 

 

1. 선택 정렬(Selection Sort)의 기본 개념

 

선택 정렬(Selection Sort)를 간단하게 정의하면, 주어진 데이터 중 최소값을 찾아서, 계속 맨앞으로 위치를 바꾸면서 순서를 바꾸는 방법입니다. 

 

 

그림을 보면서 이해하면 더 쉽게 이해할 수 있습니다. 

(출처: en.wikipedia.org/wiki/Selection_sort)

 

 

위의 사진에서 보이는 것처럼 주어진 숫자 중 3이 가장 최소값이어서 자리를 바꾼다면 6과 자리를 바꾸게 되겠죠. 이런식으로 하나하나 계속 비교하면서 자리를 찾아가는 방법입니다.

 

기본 개념을 3단계로 요약하면 다음과 같습니다. 

 

1단계. 주어진 데이터 중, 최소값을 찾습니다. 

 

2단계. 최소값을 맨 앞으로 이동합니다. 

 

3단계. 맨 앞 데이터를 제외한 나머지 데이터들에게 동일한 반복을 시행합니다. 

 

 

2. 선택 정렬의 예시와 원리 파악

 

(1) 선택 정렬의 예시: 리스트 [9, 4, 2, 1]의 경우

 

첫 번째 시행의 경우

 

최소값은 1이니까 위치는 맨앞으로 이동하고, 그 결과는 1, 4, 2, 9가 됩니다. 

 

두 번째 시행의 경우

 

최소값은 2가 되고 4와 위치가 바뀌게 되겠죠. 그래서 결과는 1,2,4,9로 이동하게 되고 정렬은 끝나게 됩니다. 

 

 

(2) 손 코딩을 통한 원리 파악

 

원리1. 최대 반복 회수는 n - 1번 

 

원리 2. 초기 최소값을 지정한다.

 

원리 3. 나머지 숫자 중 초기 최소값과 비교하여 더 작은 숫자가 있으면 초기 최소값과 위치를 바꾼다. 

 

 

3. 실제 코드 구현 및 예시를 통한 이해 

 

 

def selection_sort(data):
    for stand in range(len(data)-1):
        lowest = stand
        
        for num in range(stand+1, len(data)):
            if data[num] < data[lowest]:
                lowest = num
                
        data[stand], data[lowest] = data[lowest], data[stand]
    
    return data

 

위의 코드는 손코드로 구성한 논리를 단순히 코드로 옮겨놓은 것뿐입니다. 

 

항상 강조드리지만, 손코드와 미리 논리를 구상한 것과 안 한 것은 정말 하늘과 땅 차이의 결과를 만들어 낼 것입니다. 

 

위의 코드로 실제로 정렬을 해보도록 하겠습니다. 

 

 

선택 정렬의 실제 예시 

 

초기 난수로 생성된 10개의 리스트 숫자들이, selection sort  함수로 인해서 자연스럽게 정렬된 모습을 볼 수 있습니다.

 

따라서 이러한 코드를 작성해보는 연습을 하시다보면, 자신만의 알고리즘을 만드는데 익숙해지실 것이라 생각합니다.