[정렬 알고리즘] 예제1 - 선택 정렬(Selection Sort) (159p)

[이코테] 예제1 - 선택 정렬(Selection Sort)(159p) 

풀이 시간: 10분 이내

 

1) 문제 해결 아이디어

<선택 정렬>

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복

(최솟값을 맨 앞에 있는 값과 바꾸고 그 다음 최솟값을 앞에서 2번째 값과 바꾸는 과정을 반복)

평균 시간 복잡도: O(n**2)

공간 복잡도: O(n)

 

<파이썬 swap>

swap: 리스트에서 두 변수의 위치를 변경하는 작업

파이썬에서는 간단하게 swap를 할 수 있음(tmp 사용할 필요X)

arr = [1, 2, 3, 4, 5]

# 0번째 & 1번째 값 서로 바꾸기
arr[0], arr[1] = arr[1], arr[0]

 

2) 소스코드

# 선택 정렬(Selection Sort)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# 오름차순 정렬
# 리스트 길이만큼 반복
for i in range(len(array)):
  min_idx = i      # 최솟값 인덱스
  for j in range(i + 1, len(array)):
    if array[min_idx] > array[j]:
      min_idx = j  # 최솟값 인덱스 갱신
  # swap(최솟값과 첫값 위치 변경)
  array[i], array[min_idx] = array[min_idx], array[i]

print(array)