선택 정렬

선택 정렬이란?

선택 정렬은 배열의 길이만큼 루프를 돌며, 루프를 돌 때 마다 가장 작은 값을 “선택!” 해서 맨 왼쪽으로 옮겨가며 정렬한다. 따라서 한 번 루프를 돌때 마다 매번 최소값이 왼쪽에 정렬 된다(물론 내림차순 정렬이라면 최대값을 왼쪽으로 보내면 된다). 코드를 보면 이해가 쉽다.

과정

위와 같이 정렬 되어있지 않은 배열이 있다. 정렬을 하는과정은 아래 과정의 반복이다.

1. 정렬된 배열을 제외하고 모든 요소를 방문하여 최소값을 찾는다.

2. 찾은 최소값을 정렬되지 않은 범위에서 가장 왼쪽에 놓는다. (이렇게 되면 루프 한번에 한개의 요소가 정확히 정렬 된것이다. 제일 작은 것이 제일 왼쪽에 왔으니까!)

3. 두 번째 루프부터는 정렬된 초록색 배열 부분을 제외하고 1번 2번을 동일하게 진행한다.

즉 이렇게 배열 길이만큼의 루프를 돌며 반복하면 모든 요소가 정렬된다.

코드

def selection(arr):
  for i in range(len(arr)-1):
    minVal = arr[i] # 루프를 돌 때 마다 일단 최소값을 배열되지 않은 것들중 맨 처음 요소로 잡는다.
    index = i # 최소값을 가진 인덱스
    for j in range(i+1,len(arr)):
      if minVal > arr[j]:
        minVal = arr[j]
        index = j
    arr[index], arr[i] = arr[i], minVal 
  return arr
print(selection([5,4,3,2,1]))

시간복잡도

• 평균 : O(n^2)
• 최악 : O(n^2)