선택 정렬 - 파이썬

선택 정렬(Selection Sort) 알고리즘

구현 아이디어
1. 매 루프마다 최대 원소를 찾는다
2. 최대 원소와 마지막 원소를 교환한다.
3. 마지막 원소를 제외시킨다
4. 하나의 원소만 남을 때까지 반복한다.

def SelectionSort(result,n): #result:List, n:원소의 개수
  for i in range(n-1,0,-1): #마지막 원소를 제외
  	  #최대 원소 찾기
      max_index = 0
      for j in range(1,i+1):
          if result[j] > result[max_index]:
              max_index = j

	  #최대 원소와 마지막 원소 교환
      tmp = result[i]
      result[i] = result[max_index]
      result[max_index] = tmp

전체 원소를 비교하는 횟수 : $n-1 + n-2 + ... + 1 = n*(n-1)/2$
시간복잡도 : $O(n^2)$