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

들어가기 앞서

 

해당 문제 및 해설은 "이것이 코딩 테스트다 with 파이썬" 책을 기준으로 요약 및 정리 하여 작성하였습니다. 
 
이번 챕터에서 배울 퀵정렬은 삽입정렬과 선택정렬에 비해 어려운 편이지만, 가장 많이 사용되는 알고리즘 입니다.
이해가 더욱 잘되도록 천천히 설명할 예정이니, 같이 진행해보자.

 

 

챕터 순서

 

1. 선택 정렬 알고리즘

2. 삽입 정렬 알고리즘

3. 퀵 정렬 알고리즘

4. 계수 정렬 알고리즘

 

 

http://www.yes24.com/product/goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

 

---

 

정렬 알고리즘

 

정렬 이란, 데이터를 특정한 기준에 따라서 순서대로 나열 하는 것을 말한다.
알고리즘 효율성을 쉽게 이해할 수 있는 정렬을 통하여 코딩 테스트 합격률을 높여보도록 한다. 
정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 정리 해보려고 한다.

 

 

퀵 정렬 알고리즘

 

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

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

퀵 정렬에는 피벗(기준 점)이 사용 된다.
큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라 한다.

피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 퀵 정렬을 구분하는데,
이 책에서는 가장 대표적인 분할 방식인 호어 분할 방식을 기준으로 퀵 정렬을 설명한다.

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

 

---

 

퀵 정렬 그림 설명

I  파트

 

 단계 0   리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 '5' 이다. 이 후에 왼쪽부터 '5' 보다 큰 데이터를 선택하므로 '7' 이 선택되고, 오른쪽에서부터 '5' 보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 두 데이터의 위치를 서로 변경한다. 

 

 

 

  

 단계 1   그 다음 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. 찾은 뒤에는 두 값의 위치를 서로 변경하는데, 현재 '9' 와 '2' 가 선택 되었으므로 이 두 데이터의 위치를 변경한다.

 

 

 

 

 단계 2   그 다음 다시 피벗보다 큰 데이터와 작은 데이터를 찾는다. 단 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 것을 알 수 있다. 이렇게 두 값이 엇갈린 경우에는 '작은 데이터' 와 '피벗' 의 위치를 서로 변경한다. 즉, 작은 데이터인 '1' 과 피벗인 '5' 의 위치를 서로 변경하여 분할을 수행한다.

 

 

 

 

 단계 3  분할 완료 이와 같이 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴보자. 이제 '5' 의 왼쪽에 있는 데이터는 모두 '5' 보다 작고, 오른쪽에 있는 데이터는 모두 '5' 보다 크다는 특징이 있다. 이렇게 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 분할 또는 파티션 이라고 한다.

 

 

 

 

이 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 정렬 시키면 어떻게 될까? 

'5' 를 기준으로 왼쪽은 '5' 보다 작은 숫자로 이루어져 있고, 오른쪽은 '5' 보다 큰 숫자로 이루어져 있다.

따라서 왼쪽 리스트와 오른쪽 리스트에서도 각각 피벗을 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대하여 모두 정렬이 이루어질 것이다.

 

 

 

I I 파트

 

왼쪽 리스트에서는 다음 그림과 같이 정렬이 진행된다.

 

 

 

 

I I I 파트

 

오른쪽 리스트에서는 다음 그림과 같이 정렬이 진행된다.

 

 

 

 

 퀵 정렬은 '재귀 함수' 와 동작 원리가 같다.

 실제로 퀵 정렬은 재귀 함수 형태로 작성햇을 때 구현이 매우 간결해진다.

 

퀵 정렬이 끝나는 조건은 언제일까?

 

리스트의 데이터 개수가 1개 인 경우이다.

아래 그림을 보면서 이해를 해보자.

 

 

 

 

소스 코드 

 

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 : # 엇갈렸다면 작은 right -= 1 데이터와 피벗을 교체
        	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)

# 출력 결과
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

 

 

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

 

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))
 
 
 # 출력 결과
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

 

 

퀵 정렬의 시간 복잡도

 

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

앞서 다루었던 두 정렬 알고리즘 (선택, 삽입) 에 비해 매우 빠른 편이다.

 

컴퓨터공학과 학부에서 퀵 정렬을 공부할 때에는 퀵 정렬의 수학적인 검증에 대해서도 공부하지만, 

코딩테스트를 준비하는 과정에서는 그림을 통해 직관적인 이해를 하는 것 만으로도 충분하다.

 

실제 데이터 개수가 많아지면 많아질 수록 다른 알고리즘 보다 빠르다.

물론 최악의 경우에는 O(N^2) 이다.