- 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것
- 선택 정렬이란 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 행위
1. 선택 정렬 동작 예시
[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)
'CodingTest > 정렬 알고리즘' 카테고리의 다른 글
두 배열의 원소 교체 (0) | 2022.07.08 |
---|---|
정렬 알고리즘 종류와 특징 비교하기 (0) | 2022.07.08 |
계수 정렬 (0) | 2022.07.08 |
퀵 정렬 (0) | 2022.07.08 |
삽입 정렬 (0) | 2022.07.08 |