[알고리즘] 정렬 알고리즘 part2

퀵정렬

퀵정렬 알고리즘은 병합 정렬 알고리즘과 양대산맥으로 nlogn 시간 복잡도를 갖고있는 알고리즘으로 정렬 라이브러리의 근간이 되는 알고리즘이다.

퀵정렬의 동작 방식

퀵정렬은 3가지로 구분하여 보는게 편하다.
1. 피벗을 정하고 피벗을 기준으로 원소들의 위치를 변경시킨다.
2. 좌측 리스트들을 1번 과정을 시킨다.
3. 우측 리스트들을 1번 과정을 시킨다.

따라서 위의 과정을 거치다 보면 하나의 원소만 남게되거나 없게 되는게 최종적으로 basecase가 되며, 마지막엔 정렬된 하나의 리스트만 남게된다.

퀵정렬의 특징은 합병정렬과는 다르게 리스트 내부에서 동작이 가능하다는 점이다.

위의 동작과정을 파이썬 코드로 나타내면 아래와 같다.

def quicksort(array, start, end):
    #base case
    if start >= end:
        return
    else:
        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[right], array[left] = array[left], array[right]

        quicksort(array, start, right-1)
        quicksort(array, right+1, end)
        return array

위의 코드를 좀더 파이썬스럽게 바꾸면 아래와 같다.

def quick_py(array):
    if len(array) <= 1:
        return
    else:
        pivot = array[0]
        last = array[1:]

        left_side = [x for x in last if x <= pivot]
        right_side = [x for x in last if x > pivot]

        return quick_py(left_side) + [pivot] + quick_py(right_side)

피벗을 기준으로 왼쪽 오른쪽으로 나눌때 맨 처음 코드보다 비교 연산횟수가 많으므로 시간을 많이 잡아먹긴 하겠지만, 더 직관적이고 기억하기 쉽다.

시간 복잡도는 평균적으로 O(NlogN)이나 최악의 케이스(pivot 뽑기운)는 O(N^2)가 된다.

계수 정렬

계수정렬은 특정한 조건에 부합할 때만 사용 가능하지만 매우 빠른 정렬 알고리즘이다.

계수정렬은 모든 범위를 담을 수 있는 리스트를 선언한 뒤 해당 인덱스에 카운트를 증가시키는 방법으로 기록한다. 이처럼 계수 정렬방식은 직접 데이터의 값을 비교하는 것이 아니다. (비교기반 정렬 알고리즘이 아님.)

계수정렬을 파이썬 코드로 구현하면 아래와 같다.

def countingsort(array):
	count = [0] * (max(array) + 1)
    answer = []
    for i in range(len(array)):
    	count[array[i]] += 1
    
    for i in range(len(count)):
    	for _ in range(count[i]):
        	answer.append(i)
    return answer.

계수정렬의 시간복잡도는 O(N+K)이다. 때문에 데이터의 범위만 적절하다면 기수정렬과 마찬가지로 가장 빠른 알고리즘이라고 볼 수 있다.
그러나 공간복잡도에서 심각한 비효율성을 초래할 수 있기 때문에 해당 알고리즘은 데이터의 범위에 대해서 많이 유의해야만 한다.

python에서의 정렬 라이브러리의 시간 복잡도

일반적으로 python의 sorted함수는 최악의 경우에도 O(NlogN)의 시간 복잡도를 제공한다.