CH 02. 선택 정렬
- 여러개의 원소를 저장하는 방법
1) 배열 : 모든 원소가 정렬 (=인덱스, 0부터 시작), 임의의 원소값 탐색 시 유용
2) 연결 리스트 : 각 원소에 다음 원소 주소 저장, 삽입/삭제 시 유용
| 배열 | 리스트 | |
| 읽기 | O(1) | O(n) |
| 삽입 | O(n) | O(1) |
| 삭제 | O(n) | O(1) |
- 선택 정렬 : 목록의 모든 원소를 비교, 매 단계마다 가장 작은 원소를 앞으로 보내서 비교하는 방식, O(n^2)
# 가장 작은 값을 찾는 함수
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
# 선택 정렬
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
print(selectionSort([5, 3, 6, 2, 10]))
참고자료
Hello Coding 그림으로 개념을 이해하는 알고리즘
