기준에 따라 데이터를 정렬

선택 정렬

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 시간 복잡도는 O(N^2)이다.
선택 정렬을 이용하는 경우 데이터 개수가 10000개 이상이면 속도가 급격히 느려진다.

for i in range(n):
	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]

삽입 정렬

정렬하려는 데이터 앞 쪽의 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.
다시 말해 특정한 데이터 왼쪽에 있는 데이터들은 이미 정렬된 상태이므로, 자기보다 작은 데이터를 만나기만 했다면
더 이상 살펴볼 필요도 없이 그 자리에 삽입되면 된다.

시간 복잡도는 O(N^2)인데 정렬이 거의 되어 있는 상황에서는 시간 복잡도가 O(N)으로 퀵 정렬보다 강력하다.

for i in range(1, len(array):
    for j in range(i, 0, -1):
    	if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
       	    break

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
퀵 정렬의 평균 시간복잡도는 O(NlogN)이지만 데이터가 이미 정렬되어 있는 경우에는 O(N^2)로 매우 느리게 동작한다.

def quick(array):
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    tail = array[1:]
    
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

계수 정렬

모든 범위를 담을 수 있는 크기의 리스트를 선언하고 데이터를 하나 씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. 시간 복잡도는 O(N+K)이다. 계수 정렬은 데이터의 크기가 한정되어 있고, 많이 중복되어 있을수록
유리하며 항상 사용할 수는 없다.

코딩 테스트에서 정렬 사용법

문제에서 별도로 요구가 없다면 기본 정렬 라이브러리를 사용하고, 데이터 범위가 한정되어 있고, 더 빠르게 동작해야
하는 경우에는 계수 정렬을 사용하자!