선택 정렬

• 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 선택 정렬이란 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 행위

---

1. 선택 정렬 동작 예시

출처 : 이코테2021

 

[Step 0]

• 처리되지 않은 데이터 중 가장 작은 '0'을 선택해 가장 앞의 '7'과 바꾼다.

 

[Step 1]

• 이렇게 [Step0]에서 '0'이 '7'과 자리가 바뀐것을 알 수 있다.
• 처리되지 않은 데이터 중 가장 작은 '1'을 선택해 가장 앞의 '5'와(0은 바꿨으므로 무시) 바꾼다.

 

[Step 2]

• 처리되지 않은 데이터 중 가장 작은 '2'를 선택해 가장 앞의 '9'와 바꾼다.

 

[Step 3]

• 처리되지 않은 데이터 중 가장 작은 '3'을 선택해 가장 앞의 '7'과 바꾼다.

 

• 최종적으로 완성된다.
• 이중 반복문으로 선택정렬을 구현할 수 있다.

---

2. 선택 정렬 소스코드

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
    min_index = i #가장 작은 원소
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] #스와프
print(array)

• 맨 앞으로 보낼 인덱스 표시 (i)
• 맨 앞이 가장 작으므로 min_index는 가장 작은 원소
• 현재 위치를 나타낼 인덱스 표시(j)
• 만일 현재원소보다 더 작은 원소가 있다면 min_index를 j로 업데이트
• 안쪽 반복문이 끝나면 min_Index에는 가장 작은 원소가 들어가 있다.
• 스와프 진행

---

3. 새롭게 알게 된것

• 스와프
  • 자바나 c에서는 제3의 변수가 있어야 값을 변경할 수 있지만 파이썬에서는 특별한 라이브러리 없이 가능

a, b = b, a

---

4. 선택 정렬의 시간 복잡도

전체 연산 횟수

• 선택 정렬은 N번만큼 가장 작은 수를 찾아서 맨 앞으로 보낸다.
• 즉 (N^2 + N - 2) 

빅오표기법