[알고리즘] 퀵 정렬(Quick Sort) 정리 및 예제

해당 포스팅은 'Hello Coding 그림으로 개념을 이해하는 알고리즘' 도서를 개인공부하면서 정리한 내용입니다. 소스코드는 도서, 깃허브, 출판사 제공파일을 참고하였습니다. 깃허브 링크는 하단에 남겨두었습니다. 

 

| 문제

배열을 퀵 정렬을 이용하여 오름차순으로 정렬하라. 

 

 

| 해결

1.pivot 기준값 설정

2.두개의 하위 배열로 분할 

-배열을 기준 원소보다 작은 원소의 배열, 기준원소보다 큰 원소의 배열

3.하위 배열을 재귀적으로 퀵정렬 함수 호출

 

 

| 퀵정렬에 필요한 개념 및 주의점 

1.리스트 병합

+, extend(), sum() 중 여기서는 +를 이용한 병합을 진행.

return quicksort(less) + [pivot] + quicksort(greater)

이때 pivot은 pivot = arr[0]으로 pivot의 타입은 <class 'int'>이다. 

[pivot]이 아닌 pivot을 넣으면 타입에러가 발생한다. 즉 [pivot]으로 작성해야한다.

TypeError: can only concatenate list (not "int") to list

 

---

2.퀵정렬 Quick Sort

 

(1) 퀵 정렬 개념 

퀵정렬은 분할 정복의 전략 중 하나이다. 분할정복(divide and conquer)은 재귀적 알고리즘이다. 재귀적 알고리즘이란 함수가 자기 자신을 호출하는 재귀함수로 구성된 절차이다. 즉 퀵정렬은 재귀알고리즘을 사용하기 때문에 기본 구성은 재귀 함수와 비슷하다. 기본단계와 재귀단계로 구성된다.

 

-기본단계 base case: 함수 스스로를 다시 호출하지 않는 부분이다. 무한 반복(loop)을 방지하기 위한 단계이다.

-재귀단계 recursive case: 함수 스스로를 다시 호출하는 부분이다. 

 

(2) 퀵 정렬과 분할 정복의 관계

정렬할 배열을 기본단계 즉, 더 이상 정렬을 할 필요가 없는 배열(배열의 크기가 0개, 1개)일 때까지 배열을 분할해야한다. 분할을 지속적으로 진행하면서 재귀가 사용된다.

 

(3) 퀵 정렬과 재귀의 관계

재귀를 적용하면

하위 배열이 각각 배열의 크기가 2개 이상일 경우 재귀함수를 호출하여 정렬을 진행한다. 

하위 배열의 크기가 1일 경우 이미 배열이 완료된 상태, 즉 더 이상 정렬을 할 필요가 없는 상태로 그대로 배열을 반환한다.

 

분할 partitioning: 기준 원소(pivot)를 결정 후 하위 배열 2개를 다음과 같이 구성한다.

(A) 기준원소의 값보다 작은 값을 가지는 원소를 모은 배열

(B) 기준원소의 값보다 큰 값을 가지는 원소를 모은 배열 

 

 

(A) 기준원소의 값보다 작은 값을 가지는 원소를 모은 배열

less = [item for item in arr[1:] if item <= pivot]

 

(B) 기준원소의 값보다 큰 값을 가지는 원소를 모은 배열

greater = [item for item in arr[1:] if item > pivot]

---

 

3.슬라이싱 slicing

슬라이싱은 특정 범위 내의 값을 가져오는 기능을 한다. 

아래 코드에서 arr[1:]은 arr 배열의 두번째 원소부터 마지막 원소까지 값을 가져온다. 첫번째 원소를 가져오지 않은 이유는 pivot이 여기 코드에서는 첫번째 원소의 값을 갖기 때문이다. 굳이 첫번째 원소와 첫번째 원소를 비교할 필요가 없기 때문에 두번쨰 원소부터 범위를 지정했다.

less = [item for item in arr[1:] if item <= pivot]
greater = [item for item in arr[1:] if item > pivot]

 

 

| 전체 코드

def quicksort(arr):
    if len(arr) < 2:
        return arr
        #배열이 이미 정렬된 상태이기 때문에 배열 그대로 반환
    else:
        pivot = arr[0] #pivot 결정은 여기서는 첫번째 원소로 지정
        less = [item for item in arr[1:] if item <= pivot]
        greater = [item for item in arr[1:] if item > pivot]
        return quicksort(less) + pivot + quicksort(greater)


my_list = [77,22,66,333,888,11,0]
print('퀵정렬 결과',quicksort(my_list))

 

실행 결과

 

---

 

| 추가 문제 

리스트에서 가장 큰 수를 찾아보세요. 

(해당 문제는 연습문제 파트입니다.)

 

| 나만의 전략

기존 퀵정렬에서 기준 원소(pivot)에 저장된 값보다 (1)큰 값을 갖는 배열, (2)작은 값을 갖는 배열, 2개의 하위배열을 구성했다. 하지만 이번 문제는 가장 큰 수를 찾기만 하면 되기 때문에 작은 값을 갖는 배열을 구하지 않고, pivot보다 큰 값을 갖는 배열을 찾아가 결국 최종적으로 큰 수만 갖는 배열을 리턴하기로 한다.

pivot은 최악의 실행결과를 방지하기 위해 배열의 중간값을 갖기로 한다. 

 

| 소스코드

def recursive_max(list):
    if len(list) == 1:
        return list
    else:
        pivot = (0+ len(list) -1) //2
        greater = [item for item in list if item > list[pivot] ]
        return recursive_max(greater)
print(recursive_max([4,6,1,9,0,1001,3]))

실행결과&nbsp;

 

| 공부 도서 및  소스코드 깃허브 주소

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9788968483547 

Hello Coding 알고리즘 - 교보문고

https://github.com/egonSchiele/grokking_algorithms/blob/master/04_quicksort/python/05_quicksort.py

GitHub - egonSchiele/grokking_algorithms: Code for the book Grokking Algorithms (https://amzn.to/29rVyHf)

 

 

알고리즘은 처음 공부하는 단계입니다. 오류가 있으면 지적해주시면 감사하겠습니다.