[Algorithm] 정렬(2) - 퀵정렬, 계수 정렬

! 정렬에 대해 배우기 두 번째 시간. 이번에는 퀵 정렬과 계수 정렬에 대해 공부한 내용을 정리하고자 한다.

1. 퀵 정렬이란

퀵 정렬은 앞서서 배웠던 선택 정렬, 삽입 정렬과 같은 정렬 알고리즘들 중에서 가장 많이 사용되는 알고리즘 이다. 아마 그 만큼 빠르기 때문이 아닐까!

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

이 퀵 정렬엔 피벗(Pivot)이 사용된다. 이 피벗이라는 것은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'에 해당하는 것이다. 퀵 정렬을 수행하는데 있어서 피벗을 어떻게 설정할 것인지 미리 명시를 해야 한다.
피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 이 책에서는 호어 분할 방식을 기준으로 퀵 정렬을 설명 했다.

(다른 방식도 한번 찾아보자🤣)

- 호어 분할 방식

먼저 다음 규칙으로 피벗을 설정한다.

• 리스트에서 첫 번째 데이터를 피벗으로 정한다.

그 뒤에 왼쪽에서 피벗보다 큰 데이터를 찾고, 오른쪽에서 피벗보다 작은 데이터를 찾는다. 그 후에 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.

다음 단계부터는 그림을 통해 자세히 알아보자

• 1단계
  

리스트의 첫 번째 데이터를 피벗으로 설정하는 기준으로 피벗은 '4'이다. 이후에 왼쪽에서 '4'보다 큰 데이터를 선택하면 '7'이 선택 되고, 오른 쪽에서 '4'보다 작은 데이터를 선택하면 '3'이 선택 된다. 다음으로 이 선택된 두 데이터의 자리를 바꿔준다.

• 2단계
  
  1단계 실행 결과 '3'과 '7'의 자리가 바뀌었다. 다음은 마찬가지로 왼쪽에서 '4'보다 큰 데이터, 오른쪽에서 '4'보다 작은 데이터를 선택한 후 자리를 바꾼다. 여기서 '5'와 '1'이다.

• 3단계
  
  마찬 가지로 '6'과 '0'의 자리도 바꿔준다.

• 4단계
  
  이 부분이 상당히 중요하다. 이제 왼쪽에서 찾는 값과 오른쪽에서 찾는 값의 위치가 서로 엇갈린다. 이렇게 두 값이 엇갈린 경우에는 '작은 데이터'와 '피벗'의 위치를 서로 변경한다. 즉 여기서 '4'와 '0'의 위치를 서로 변경하여 분할을 수행한다.
  
  분할 작업을 완료한 후에 보면 피벗이였던 '4'의 왼쪽의 데이터는 '4'보다 작고 오른쪽 데이터는 '4'보다 크다. 이러한 작업을 분할 혹은 파티션 이라과 한다!

• 5단계
  이와 같이 분할 작업을 한 이후에 왼쪽 데이터인 '0'과 오른쪽 데이터인 '6'을 다시 피벗으로 설정하여 각각의 정렬 작업을 진행해주면 정렬이 이루어지게 된다.

퀵 정렬의 경우 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다!!
그러면 재귀 함수로 작성을 했는데 끝나는 조건을 어떻게 설정해야할까?
바로 현재 리스트의 데이터 개수가 1개인 경우이다.

• 코드구현

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

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^2)에 비해 매우 빠른 편이다.

여기서 중요한 점은 최악의 경우 O(N^2)이라는 것이다. 삽입 정렬의 경우에는 '이미 데이터가 정렬되어 있는 경우'에 매우 빠르게 동작이 이루어진다. 하지만 퀵 정렬은 이와 달리 '이미 데이터가 정렬되어 있는 경우' 매우 느리게 동작하고, 오히려 데이터가 무작위로 입력되어 있는 경우에 빠르게 동작할 확률이 높다. 그러므로 우리는 적절한 상황에 적절한 정렬 방식을 사용할 필요성이 있다!!

2. 계수 정렬

계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 예를 들어 모든 데이터가 양의 정수라고 해보자. 데이터의 개수가 n, 데이터 중 최댓값이 k일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다.

그러면 계수 정렬을 사용할 수 있는 조건은 무엇 일까?
바로 '데이터의 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때' 만 사용이 가능하다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

이러한 특징을 가지는 이유는 계수 정렬을 이요할 때 '모든 범위를 담을 수 있는 크기의 리스트를 선언'해야하기 때문이다.

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

계수 정렬은 데이터의 앞서 말했듯이 데이터의 개수가 제한되어 있을 때에 한해 데이터의 개수가 매우 많더라도 빠르게 동작한다.

- 작동 과정

• 초기 단계 : 7 5 9 0 3 1 5 2 9 1 4 8 0 5 2

먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 여기서는 '9'가 가장 큰 데이터이고, '0'이 가장 작은 데이터이다. 그러므로 우리는 0~9까지 담길 크기가 10인 리스트를 다음과 같이 선언해준다.

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0

• 1단계

첫 번째 데이터인 '7'과 동일한 인덱스인 '7' 데이터를 1씩 증가시킨다.

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	1	0	0

• 2단계

마찬 가지로 두 번째 데이터인 '5'와 동일한 인덱스인 '5' 데이터를 1 증가시킨다.

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	1	0	1	0	0

• 결과

이와 같은 방식으로 계속 진행할 경우 다음과 같이 리스트에 각 데이터가 몇번 나왔는지 횟수가 기록된다.

0	1	2	3	4	5	6	7	8	9
2	2	2	1	1	2	1	1	1	2

그 뒤에 리스트의 첫 번째 데이터부터 값만큼 인덱스를 출력하면 된다.

출력 : 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

- 코드 구현

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

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)이다. 이와 같은 시간 복잡도는 현존하는 정렬 알고리즘 중에서 기수 정렬과 더불어 가장 빠르다고 보여진다.

이상 4가지 정렬 알고리즘에 대해 정리해봤다!!👍