[알고리즘] 선택 정렬

1. 선택 정렬 개념
2. 선택 정렬 예시
3. 선택 정렬 구현 (With Python3)
4. 선택 정렬 특징

 

선택 정렬 개념

• 제자리 정렬 알고리즘의 하나로, 다음의 순서를 반복해서 정렬하는 알고리즘
  • 주어진 데이터 중, 최솟값을 찾는다.
  • 해당 데이터를 가장 맨 앞의 데이터와 교체
  • 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

출처 : https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

 

선택 정렬 개념

• 만일 [3,4,5,1,2]을 정렬한다고 하면 리스트의 최솟값은 1이므로 0번째 인덱스인 3과 값을 교환한다. 그 결과는 [1,4,5,3,2]. 그다음 리스트에서 1을 제외한 최솟값은 2이므로 1번째 인덱스인 4와 값을 교환한다. 그 결과는 [1,2,5,3,4]. 그다음 리스트에서 1,2를 제외한 최솟값은 3이므로 2번째 인덱스인 5와 값을 교환한다. 그 결과는 [1,2,3,5,4]. 이런 방식으로 반복해 정렬을 진행한다.
• n개의 데이터를 선택 정렬로 정렬하면 1,2,...,n 번 반복할 때마다 정렬된 데이터를 제외한 1,2,..., n번째로 최솟값을 구하게 된다.

 

선택 정렬 예시

• 선택 정렬을 이용하여 [5,4,2,1,3]을 오름차순으로 정렬시

선택 정렬 예시

• 첫 번째 바퀴
  • 리스트에서 최솟값이 1이므로 0번째 인덱스의 값인 5와 교환한다. 여기서 1은 정렬된 상태이다.
• 두 번째 바퀴
  • 리스트에서 정렬되지 않은 데이터 중 최솟값이 2이므로 1번째 인덱스의 값인 4와 교환한다. 여기서 2는 1과 마찬가지로 정렬된 상태이다.
• 세 번째 바퀴
  • 리스트에서 정렬되지 않은 데이터 중 최솟값이 3이므로 2번째 인덱스의 값인 4와 교환한다. 여기서 1,2,3은 정렬된 상태이다.
• 네 번째 바퀴
  • 리스트에서 정렬되지 않은 데이터 중 최솟값이 4이므로 3번째 인덱스의 값인 5와 교환한다. 여기서 1,2,3,4는 정렬된 상태이다.
• 원소가 한 개만 남으므로 최종적으로 [1,2,3,4,5]가 오름차순으로 정렬된 리스트임을 확인한다.

 

선택 정렬 구현 (With Python3)

def selectionSort(x):
    
    for i in range(len(x) - 1):
        min = i
        for j in range(i+1, len(x)):
            if x[min] > x[j]: # 최솟값을 구하는 과정
                min = j
        x[i], x[min] = x[min], x[i]

    return x
                
if __name__ == "__main__":
    
    x = [5,4,2,1,3]
    
    selectionSort(x)

 

선택 정렬 특징

• 시간 복잡도
  • 반복을 두 번 실행하므로  $$O(n^2)$$