"선택"
하는 알고리즘[선택 정렬 과정]
1. 앞에서부터 데이터 하나를 선택한다.
2. 내가 선택한 데이터 이후에 있는 우너소들 중 가장 작은 값을 찾는다.
3. 내가 선택한 값과 바꾼다.
데이터의 개수가 n개라고 가정했을 때,
n-1
n-2
(n-1) + (n-2) + ... + 2 + 1
▶︎ n(n-1)/2
* 비교하는 것이 상수 시간에 이루어진다는 가정하에,
* n개의 주어진 배열을 정렬하는데 O(n^2)만큼의 시간이 걸린다.
* 최선, 평균, 최악의 경우 시간복잡도는 O(n^2)으로 동일하다.
1. 제일 작은 숫자를 찾기 위해 순차적으로 이동
2. Outer 루프가 한번 돌때마다 element 하나의 최종 위치가 확정
3. 탐색 범위
- Outer : 0 -> n-1
첫번째 element를 가장 낮은 숫자로 가정
- Inner : 0 -> i+1
이미 정렬된 부분을 제외
가장 낮은 숫자(i) 다음 인덱스부터 비교
4. Time Complexity
- worst : O(n^2)
- Average : O(n^2)
- Best : O(n^2)
def selectionSort(arr):
n = len(arr)
for i in range(n-1):
min = i
for j in range(i+1, n):
if arr[min] > arr[j]:
min = j
arr[i], arr[min] = arr[min], arr[i]
arr = [-2, 45, 0, 11, -9,88,-97,-202,747]
selectionSort(arr)
print(arr)
재승님 ~ 취업 축하드려요!! 역시 똑똑한 개발자는 다르시군요 취업하시고도 블로그 자주 써주세요~!