Advanced Algorithm - 퀵 정렬(Quick Sort)

1. Quick 정렬이란? 

- 정렬 알고리즘의 꽃! 파이썬과 만나면 아름다운 코드가 탄생한다. 

- 데이터에서 기준점(pivot)을 정하여 pivot보다 작다면 좌측(left)에, 크다면 우측(right)에 정렬한다.

- 좌/우측으로 1차 정렬된 데이터에서 좌/우측 각각의 pivot을 다시 선정하고 정렬을 수행한다.

- 이 과정을 재귀함수를 사용하여 반복한다.

- 최종적으로 정렬된 데이터를 반환한다. 

 

예시) Quick 정렬의 동작과정 

index	0	1	2	3	4	5
data	55	13	45	88	76	59

이와 같은 데이터가 있을 경우, 

 

 

1) 55를 pivot으로, 좌/우측으로 정렬 

index	1	2	0	3	4	5
data	13	45	55 (pivot)	88	76	59

 

 

2) 좌/우측에서 각각 pivot을 선정하여 재정렬 (재귀함수 부분) 

 

[좌측 - 1차 정렬 후 완료]

index	1	2
data	13 (pivot)	45

 

[우측 - 1차 정렬]

index	4	5	3
data	76	59	88 (pivot)

 

[우측 - 2차 정렬 후 완료]

index	5	4
data	59	76 (pivot)

 

 

3) 정렬된 결과를 병합

index	1	2	0	5	4	3
data	13	45	55	59	76	88

 

---

2. 어떻게 코드로 구현할까? 

 

a) quick 정렬의 규칙

1. 만약 리스트 갯수가 한개이면 해당 리스트 리턴

2. 그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(pivot)으로 놓기

3. left, right 리스트 변수를 생성 

4. 맨 앞의 데이터(index 0번)를 뺀 나머지 데이터를 기준점(pivot)과 비교

   - 기준점보다 작으면 left.append(해당 데이터)

   - 기준점보다 크면 right.append(해당 데이터)

5. return quicksort(left) + pivot + quicksort(right) 로 재귀 호출

 

 

b) pivot을 맨 처음 데이터로 선정하고 두번째 데이터부터 pivot과 비교하여 분류한다.

def qsort(list):
	pivot = list[0] #첫번째 데이터 = pivot
    for n in range(1, len(list)): # 두번째 데이터(index 1번)부터 비교
    	if pivot > list[n]: 
        	left.append(list[n])
        else:
        	right.append(list[n])

 

 

c) 위의 규칙성을 재귀함수를 이용하여 풀이

def qsort(list):
	if len(list) <= 1:
    	return list
    else:
    	pivot = list[0]
    	for n in range(1, len(list)):
        	if pivot > list[n]: 
        		left.append(list[n])
        	else:
        		right.append(list[n])
        return qsort(left) + [pivot] + qsort(right) # 리스트 간의 연산으로 하나의 리스트를 생성

---

3. Quick Sort 코드구현 

 

a) 기본적인 코드구현

def qsort(data):
    if len(data) <= 1:
        return data
    else:
        pivot = data[0]
        left = list()
        right = list()
        for index in range(1, len(data)):
            if pivot > data[index]:
                left.append(data[index])
                print(f"left = {left}") #과정을 보기위한 print문 
            else:
                right.append(data[index])
                print(f"right = {right}") #과정을 보기위한 print문
        return qsort(left) + [pivot] + qsort(right)

 

 

[테스트 및 연산 과정 풀이] 

 

 

b) list comprehension을 이용한 코드 업그레이드 

def qsort(data):
    if len(data) <= 1:
        return data
    else:
        pivot = data[0]
        left = [item for item in data[1:] if pivot > item] #list comprehension
        print(f"left = {left}") #과정을 보기위한 print문
        right = [item for item in data[1:] if pivot <= item]
        print(f"right = {right}") #과정을 보기위한 print문

        return qsort(left) + [pivot] + qsort(right)

 

 

[테스트 및 연산 과정 풀이] 

---

4. Quick 정렬의 시간복잡도 

- quick 정렬의 평균적인 시간복잡도는 O(n log n)이다. 

- 다만, 맨 처음 결정되는 pivot이 가장 크거나 작은 데이터라면 모든 데이터와 비교하는 최악의 상황으로, O(n^2)의 시간복잡도를 갖는다. 

 

* 빅 오 표기법은 최악의 상황에서 알고리즘이 갖는 시간복잡도를 의미한다. 하지만, 최악의 경우는 잘 발생하지 않는다는 이유로 몇몇 알고리즘은 평균적인 시간복잡도를 기준으로 한다.