[정렬 알고리즘] 1. 선택 정렬 (Selection Sort)

선택정렬

선택 정렬은 배열을 처음부터 끝까지 돌리면서, 현재 인덱스에 들어갈 값을 찾아 바꾸는 간단한 알고리즘이다. 현재 인덱스에 들어갈 값을 정하는 기준에 따라 최소 선택 정렬 (Min-selection Sort)최대 선택 정렬 (Max-Selection Sort) 로 나뉘어 진다. 정렬 결과는 이 기준에 따라 오름차순, 내림차순으로 나뉜다. 로직 설명은 최소 선택 정렬 기준으로 한다.

선택 정렬은 O(n2)의 시간 복잡도O(n)의 공간 복잡도를 가지고 있다.

로직

  1. 주어진 배열에서 최소의 값을 찾는다.
  2. 찾은 최소의 값을 배열의 첫째값과 바꾼다.
  3. 배열의 첫번째 요소를 제외한 리스트에서 최소의 값을 찾고 위와같이 반복한다.

이해가 잘 되지 않는다면, Sort 애니메이션을 참고하자. 정렬되지 않은 부분에서 반복적으로 최소값을 찾고, 첫번째 요소와 위치를 바꾸고 있다.

소스코드 (Python)

list = [33,5,76,1,7,17,23,29,8,9,2]

for idx, val in enumerate(list):
  
  min = val
  min_idx = idx

  for j in range(idx, len(list)):
    if list[j] < min:
      min = list[j]
      min_idx = j
  
  list[idx] = min
  list[min_idx] = val
    
print (list)

직관적으로 작성해보았다.