정렬

1. 선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 (마지막 데이터는 처리 안해도 됨, 자기 자신 위치가 맨 앞이 되므로)
-> 선형 탐색, 이중 반복문

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

for i in range(len(array)): 
# i는 가장 작은 데이터와 위치가 바뀔 인덱스(앞쪽 원소의 위치)
    min_index = i 
# 앞쪽 원소가 가장 작은 원소의 인덱스가 될 수 있도록 함
    
    for j in range(i+1, len(array)): 
# 선형탐색 수행해서 작은 원소를 찾는다.
        if array[min_index] > array[j]: 
# 현재의 작은 원소보다 더 작은 원소가 있다면,
            min_index = j 
# 그 위치의 인덱스가 min_index로 담길 수 있도록 한다.
    array[i], array[min_index] = array[min_index],array[i] 
# 서로 바꿔줌, 스왑 연산

print(array)

선택정렬의 시간 복잡도 : N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

$N + (N-1) + (N-2) + ... + 2 = (N^2 + N - 2) / 2$
$=> O(N**2)$

## 2. 삽입 정렬 > ## 3. 퀵 정렬

4. 계수 정렬