정렬(2)-퀵 정렬, 계수 정렬, 라이브러리

퀵 정렬

퀵 정렬은 지금까지 배운 정렬 알고리즘 중에서 가장 많이 사용된다.

이 교재에는 없지만 병합 정렬도 퀵 정렬과 같이 빠르다.

 

퀵 정렬은 기준을 설정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

퀵 정렬에서는 기준 숫자인 피벗이 사용된다.

 

리스트에서 피벗을 정한다.

피벗을 정하고 나면 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.

그 다음 큰 데이터와 작은 데이터의 위치를 교환한다.

 

이렇게 있을 때, 5를 피벗으로 정했다. 그러면 왼쪽에선 7이 피벗보다 크고, 오른쪽에선 4가 피벗보다 작다.

따라서 7과 4의 위치를 바꿔준다.

 

이러다보면 왼쪽 리스트는 모두 피벗보다 작고 오른쪽은 모두 피벗보다 큰 데이터가 위치한다.

이렇게 위치하도록 하는 작업을 분할 혹은 파티션이라고 한다.

 

그 다음엔 왼쪽 리스트는 왼쪽 리스트의 피벗을 정해서 위 과정을 하고 오른쪽도 마찬가지로 위 과정을 하여 정렬을 완료한다.

 

-퀵 정렬 예시 코드

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

def quick_sort(lst, start, end):
  if start >= end:
    return
  pivot = start
  left = start + 1
  right = end
  while(left <= right):
    while left <= end and lst[left] <= lst[pivot]:
        left += 1
    while right > start and lst[right] >= lst[pivot]:
        right -= 1
    
    #엇갈렸을 때
    if left > right:
      lst[pivot], lst[right] = lst[right], lst[pivot]
    else:
      lst[left], lst[right] = lst[right], lst[left]
      
  quick_sort(lst, start, right-1)
  quick_sort(lst, right+1, end)
  
quick_sort(ary, 0, len(ary)-1)
print(ary)

pivot, left, right를 만들어서 퀵 정렬 과정을 이어 나간다.

엇갈리면 pivot과 right의 위치를 바꿔준다.

이 코드는 가장 직관적인 형태의 코드이다.

그리고 이 코드를 안보고 짜면서 실수했던 부분이 while문에서 인덱스 범위를 먼저 체크하는 것이 중요하다는 것을 알았다. 인덱스 번호를 먼저 체크하지 않으면 범위 에러가 발생할 수 있다.

 

-파이썬의 장점을 살린 퀵 정렬 코드

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

def quick_sort(lst):
  if len(lst) <= 1:
    return lst
  pivot = lst[0]
  tail = lst[1:]
  
  left = [i for i in tail if i <= pivot]
  right = [i for i in tail if i > pivot]
  
  return quick_sort(left)+[pivot]+quick_sort(right)

print(quick_sort(ary))

이렇게 줄일 수 있다.

왼쪽과 오른쪽을 나누고 계속 나눠서 정렬을 한다.

그리고 맨 처음 리스트의 개수를 체크할 때 1개 미만이면 리스트를 리턴해야한다.

 

-시간 복잡도

퀵 정렬은 O(NlogN)으로 선택, 삽입 정렬보다 매우 빠르다.

하지만 최악의 경우 시간 복잡도가 O(N^2)이다.

데이터가 랜덤으로 들어오면 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 데이터가 이미 정렬되어 있는 경우엔 매우 느리게 동작한다. 삽입 정렬과 반대이다.

 

계수 정렬

계수 정렬은 특정한 조건이 부합할 때만 사용 가능하지만 매우 빠르다.

모든 데이터가 양의 정수일 때, 데이터 개수가 N, 이 중 최대값이 K이면 계수 정렬은 최악의 경우에도 O(N+K)를 보장한다.

다만 계수 정렬은 데이터의 크기가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능하다.

예를 들어 성적 데이터를 정렬할 때 효과적이다. 다만 큰 데이터와 가장 작은 데이터의 차이가 너무 크면 사용할 수 없다.

계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 특징이 있다.

 

초기에 이렇게 데이터가 있다.

 

그러면 처음부터 확인하면서 그 숫자의 카운트를 올려주는 방식으로 진행한다.

이렇게하여 최종적으로 출력을 한다.

 

-계수 정렬 예시 코드

ary = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count = [0] * (len(ary)+1)

for i in ary:
  count[i] += 1

for i in range(len(count)):
      for j in range(count[i]):
        print(i, end=" ")

이런식으로 직접 세서 정렬한다.

 

-시간 복잡도

데이터 개수 N, 최대값 크기 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)이다.

 

파이썬의 정렬 라이브러리

파이썬은 기본으로 sorted() 함수를 제공한다.

sorted()는 병합 정렬을 기반으로 만들어졌다. 병렬 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 O(NlogN)을 보장한다.

또한 sort()는 리스트 객체 내장 함수로 별도의 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

 

그리고 sorted()나 sort()를 이용할 때는 key 매개변수를 입력받을 수 있다. 

예를 들어 튜플로 구성되어 있을 때 두번째 원소를 기준으로 정렬이 가능하다. 혹은 람다 함수도 사용 가능하다.

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

def setting(data):
      return data[1]

result = sorted(ary, key=setting)
print(result)

 

-시간 복잡도

정렬 라이브러리는 항상 최악의 경우에도 O(NlogN)을 보장한다. 이미 잘 작성된 함수라서 퀵 정렬을 구현할 때 보다 더욱더 효과적이다.

 

정렬 알고리즘 사용되는 경우

1. 정렬 라이브러리로 풀 수 있는 문제: 라이브러리 사용 방법을 숙지하면 어렵지 않다.
2. 정렬 알고리즘의 원리에 대해서 풀어보는 문제: 선택, 삽입, 퀵 정렬 등을 알고 있어야 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반으로 풀 수 없고 계수 정렬 등의 다른 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.