[이것이코딩테스트다with파이썬] 정렬

 

정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

선택 정렬

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고,
그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정의 반복.
데이터가 N개일 때, '가장 작은 것을 선택'하는 과정을 N-1번 반복하면 정렬이 완료된다.

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)

첫 번째 for문은 배열의 첫 번째 원소부터 확정짓기 위한 반복문,
두 번째 for문은 확정짓기 위한 원소 자리 이후의 것들부터 탐색하여
가장 수가 작은 원소의 자리를 찾기 위한 반복문이다.

파이썬에서 활용되는 swap의 코드를 잘 기억할 것! 정말 간편하다.

[선택 정렬의 시간 복잡도]

선택 정렬은 N-1번 만큼 작은 수를 찾아 맨 앞으로 보내야 한다.
따라서 연산 횟수는 N + (N-1) + (N-2) + ... + 2로 볼 수 있고,

근사치로 N*(N+1) / 2번, 즉, (N² + N) / 2번의 연산을 수행한다고 표현 가능하다.

빅오 표기법으로 간단히 O(N²)로 표현할 수 있다.

직관적으로 표현하자면, 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문이라고 이해할 수 있다.
선택 정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 매우 비효율적이다.
다만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦으므로 익숙해질 필요가 있다.




삽입 정렬

특정한 데이터를 적절한 위치에 '삽입'한다.
특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
(즉, [1,2,3,6,4]의 배열에서 4을 삽입할 때 6보다 작고 3보다 크므로 그 사이에 삽입하게 되는데,
3 앞의 데이터는 이미 정렬되어 있다고 가정하므로 선택정렬처럼 따로 비교하지 않아도 된다는 것이다.)
특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

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

for i in range(1, len(array)): 
	for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법 
    	if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동 
        	array[j], array[j-1] = array[j-1], array[j] 
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤 
        	break 
            
print(array)

[삽입 정렬의 시간 복잡도]

삽입 정렬의 시간 복잡도는 O(N²)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다.

하지만, 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하여
최선의 경우 O(N)의 시간 복잡도를 가진다.
퀵 정렬 알고리즘과 비교했을 때, 보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는
퀵 정렬 알고리즘보다 더 강력하다.




퀵 정렬

가장 많이 사용되는 알고리즘 !
퀵 정렬과 비교할 만큼 빠른 알고리즘으로는 '병합 정렬' 알고리즘이 있다.
피벗 : 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'

'호어 분할 방식'

피벗을 리스트의 첫 번째 데이터로 설정하고 왼쪽에서부터 피벗보다 큰 데이터를 찾고,
오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
피벗보다 작은 데이터 - 피벗보다 큰 데이터 순으로 모두 정렬이 된 경우
교차가 되는 시점에서 작은 데이터를 피벗과 위치 교환해주어 분할을 수행한다.
이제, 피벗 왼쪽 데이터들은 모두 피벗보다 작고, 오른쪽 데이터들은 모두 피벗보다 크다.
이 작업을 분할 혹은 파티션이라고 한다.
이제, 왼쪽 리스트와 오른쪽 리스트에서도 동일한 작업을 수행하여 정렬을 한다.


# 기존 퀵 정렬 소스코드

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] 
def quick_sort(array, start, end): 
	if start >= end: 
      # 원소가 1개인 경우 종료 
      return 
    pivot = start # 피벗은 첫 번째 원소 
    left = start + 1 
    right = end 
    while left <= right 
    	# 피벗보다 큰 데이터를 찾을 때까지 반복 
    	while left <= end and array[left] <= array[pivot]: 
        	left += 1 
        # 피벗보다 작은 데이터를 찾을 때까지 반복 
        while right > start and array[right] >= array[pivot]: 
        	right -= 1 
          if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체 
          	array[right], array[pivot] = array[pivot], array[right] 
          else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체 
          	array[left], array[right] = array[right], array[left] 
     # 분할 이후 왼쪽 부분과 오른쪽 부분에서 가각 정렬 수행 (재귀) 
     quick_sort(array, start, right - 1) 
     quick_sort(array, right + 1, end) 
     
quick_sort(array, 0, len(array) - 1) 
print(array)

# 파이썬의 장점을 살린 퀵 정렬 소스코드

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

def quick_sort(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) 
    
print(quick_sort(array))

 

피벗과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간 면에서는 조금 비효율적이다.
하지만, 더 직관적이고 기억하기 쉽다는 장점이 있다.


[퀵 정렬의 시간 복잡도]

퀵 정렬의 평균적인 시간 복잡도는 O(NlogN)이다.

최악의 경우에는 O(N²)이다. 

데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높으나,
이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다.




계수 정렬


특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
조건 : 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때
예를 들어 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우
계수 정렬은 사용하기 어렵다.
일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 100만을 넘지 않을 때 효과적으로 사용할 수 있다.
계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

계수 정렬은, 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.
처음에는 모든 데이터가 0이 되도록 초기화한다.
그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를
1씩 증가시키면 계수 정렬이 완료된다.
정렬된 결과를 직접 눈으로 확인하고 싶다면,
리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다.

# 모든 원소의 값이 0보다 크거나 같다고 가정 
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] 
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화) 
count = [0] * (max(array) + 1) 

for i in range(len(array)): 
	count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가 
    
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인 
	for j in range(count[i]]: 
    	print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 증가

 

[계수 정렬의 시간 복잡도]

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때,
계수 정렬의 시간 복잡도는 O(N+K)이다.
앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐 아니라,
추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다.
따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.


[계수 정렬의 공간 복잡도]

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
예를 들어 데이터가 0과 999,999, 단, 2개만 존재할 때에도 리스트의 크기가 100만 개가 되도록 선언해야 한다.
따라서, 항상 사용할 수 있는 정렬 알고리즘은 아니며,
동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.
반면에, 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하기 때문에
데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.

계수 정렬은 데이터의 크기가 한정되어 있고,
데이터의 크기가 많이 중복되어 있을 수록 유리하며 항상 사용할 수는 없다.
하지만, 조건만 만족한다면 정렬해야 하는 데이터의 개수가 매우 많을 때에도 효과적으로 사용할 수 있다.
계수 정렬의 공간 복잡도는 O(N+K)이다.




파이썬의 정렬 라이브러리


파이썬은 기본 정렬 알고리즘인 sorted() 함수를 제공한다.
sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데,
병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다.
이러한 sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다.
집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다.

리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수도 있다.
리스트 객체의 내장 함수인 sort()를 이용하는 것인데,
이를 이용하면 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

sorted()나 sort()를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다.
key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.
람다(lambda) 함수도 사용할 수 있다.

람다(lambda) : 익명함수를 지칭하는 용어. 즉, 기존의 함수(명 등)을 선언하고
사용하던 방식과는 달리 바로 정의하여 사용할 수 있는 함수.

 

array = [('바나나', 2), ('사과', 5), ('당근', 3)] 

def setting(data): 
	return data[1] 
    result = sorted(array, key=setting) 
    print(result)

[정렬 라이브러리의 시간 복잡도]

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.
병합 정렬 + 삽입 정렬 => 하이브리드 방식의 정렬 알고리즘을 사용한다.
단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고,
데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용해야 한다.