Elementary Sorts(2) : Selection Sort

Selection sort demo

• entry 중에서 가장 작은 것을 찾아 맨 앞의 원소와 swap하는 작업을 반복합니다.
  아주 간단한 정렬 중 하나인 '선택 정렬'입니다.
• 결과적으로 왼쪽의 원소가 오른쪽보다 반드시 작은, 오름차순 정렬이 수행됩니다.

 

Selection sort inner loop

n = len(a)
for i in range(n):
    minimum = i
    for j in range(i+1, n):
    if a[j] < a[minimum]:
        minimum = j
    a[i],a[minimum] = a[minimum],a[i]

• 파이썬으로 선택 정렬을 구현하면 위와 같습니다.
  이중 for문 내에서 가장 작은 값의 인덱스를 minimum에 저장하고, 마지막에 이를 맨 앞의 값과 교환하는 방식입니다.

 

Selection sort: mathematical analysis

• 이중 for문의 범위를 따져보면 비교하는 명령은 N^2 / 2번 수행됩니다.
  (굉장히 비효율적인 정렬 알고리즘이죠 😅)
  또한 실제로 값을 교환하는 명령은 N번 수행됩니다.
• 심지어 이미 정렬이 되어있는 배열에 대해서 정렬을 수행한다 하더라도,
  모든 값을 비교하는 과정이 이미 동일하고, 또 정렬을 추가로 수행하지 않아도 되는 상황임에도 자기 자신과 교환하는 명령 자체는 수행하기 때문에 동일한 시간 복잡도를 갖게 됩니다.
  다시 말하자면 최악과 최선의 시간 복잡도가 둘 다 똑같이 O(N^2 / 2)가 된다는 뜻입니다.

 

 

출처: Coursera, Algorithms, Part 1, Princeton University