[Hello Coding 알고리즘] 4. 퀵 정렬

[210701]

Hello Coding 알고리즘

4. 퀵 정렬

분할 정복 divide and conquer

: 문제 해결 방법 중 가장 유명한 재귀적 알고리즘.

특정 알고리즘(기술)이 아닌, 문제를 풀기 위한 방법론이다.

분할 정복의 증명 - '유클리드 호제법 Euclid's algorithm' 참고하기

예시 : 농부가 어떤 땅을 똑같은 정사각형 토지로 나누고 싶을 때.

분할 정복으로 푸는 단계.

1. 기본 단계를 찾는다. 이 부분은 가능한 가장 간단한 문제여야 한다.
2. 전체 문제가 기본 단계가 될 때까지 나누거나 작게 만든다.

분할 정복에서는 재귀 함수를 호출할 때 마다 문제를 작게 나누어야 한다.

예제

Q. 배열의 모든 숫자를 더한 합계 구하기. 반복문이 아닌 재귀 함수를 사용한다.

• 기본 단계를 찾는다.
  • (합을 구하기에) 가장 간단한 배열은? = 원소의 갯수가 0개이거나 1개인 배열
• 재귀 호출을 할 때마다 배열의 크기가 점점 감소해야 함.
  • 예를 들어, [2,3,4] 인 배열의 총합과 [2], [3,4] 배열의 총합은 같다.

즉 sum함수를 아래와 같은 방식으로 동작시킨다.

• 리스트를 받는다
  • 만약 리스트가 비어 있으면 0을 반환한다.
  • 그렇지 않으면 총합은 리스트의 첫 번째 숫자와 나머지 리스트의 총합을 더한 값이 된다.
• 예를 들어 [2,3,4] 배열의 총합을 구할 때, [2] + [3,4]의 합을, [3,4]는 [3],[4]의 합을 구해 최종 답을 9로 계산해낸다.

※ 배열을 포함하는 재귀함수를 만들 때, 기본 단계는 보통 빈 배열이나 원소가 1개인 배열이 된다.

❓ 반복문으로 풀 수 있는데 왜 재귀함수로 풀어야 하는가?

❗ 함수형 프로그래밍 functional programming을 맛보는 과정이다. 일부 함수형 프로그래밍 언어(하스켈)에는 반복문이 없다.

퀵 정렬 quicksort

: 정렬 알고리즘으로, 선택 정렬보다 훨씬 빠르고 자주 사용되는 알고리즘이다.

• 가장 빠른 정렬 방법 중 하나이다.
• 퀵 정렬은 분할 정복 전략을 사용하는 좋은 예이다.
• 퀵 정렬은 기준 원소에 따라 처리속도가 달라진다.

예제

배열을 퀵 정렬로 정렬해 보자.

• 가장 간단한 배열 정렬은?
  • 원소가 0개이거나 1개인 배열 (= 정렬할 필요가 없으므로, 있는 배열을 그대로 반환하면 됨)

  • def quicksort(array):
        if len(array) < 2:
            return array

• 원소가 2개인 배열은?
  • 첫 번째 원소가 두 번째 원소보다 작은지 확인한다.
  • 만약 그렇지 않다면 두 원소의 자리를 교환한다.
• 원소가 3개 이상인 배열은?
  • 배열에서 기준 원소pivot 를 고른다.
  • 분할 partitioning : 기준 원소보다 작은 하위 배열 - 기준 원소 - 기준 원소보다 큰 하위 배열 로 분류한다.
  • 하위 배열 sub-array : 아직 정렬되어 있지 않음. 이 하위배열들을 정렬하면 전체 배열도 정렬된 배열이 된다.
  • 하위 배열에 대해서도 재귀적으로 퀵 정렬을 호출한 다음, 그 결과를 합친다.

퀵 정렬 코드

def quicksort(array):
    if len(array) < 2: ## 기본 단계 : 원소의 개수가 0개이거나 1개일 때 (정렬할 필요가 없음)
        return array
    else: ## 재귀 단계
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot] ## 기준 원소보다 작거나 같은 모든 원소로 이루어진 하위 배열
        greater = [i for i in array[1:] if i > pivot] ## 기준 원소보다 큰 원소로 이루어진 하위 배열
        return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])

빅오 표기법 복습

아래로 갈수록 느린 알고리즘, 위로 갈수록 빠른 알고리즘

• O(logn) : 이진 탐색
• O(n) : 단순 탐색
• O(n logn) : 퀵 정렬, 병합 정렬 merge sort
• O(n제곱) : 선택 정렬
• O(n!) : 외판원 문제

퀵 정렬은 기준 원소에 따라 처리속도가 달라진다.

• 최악의 경우 O(n제곱)
• 그러나 평균적으로는 O(n logn)의 속도로 처리됨.

병합 정렬과 퀵 정렬 비교

병합 정렬O(n logn) 이고 퀵 정렬O(n logn)이지만

빅오표기법상 무시되는 상수(c, constant) 값은 퀵 정렬이 병합 정렬보다 작다.

따라서 실행 시간이 O(n logn) 으로 동일하다면 퀵 정렬이 더 빠르다(상수값이 작기 때문)

평균적인 경우 vs 최악의 경우

퀵 정렬의 성능은 '기준 원소pivot'에 크게 좌우된다.

예를 들어 같은 배열이라도..

• 최악의 경우 첫 번째 원소를 기준원소로 선택하는 경우
  • 배열의 길이(n)만큼의 콜스택 깊이를 갖게 됨 - O(n)만큼의 스택
• 최선의 경우 중간 원소를 기준 원소로 선택하는 경우
  • 대략 배열 길이 절반(n/2)만큼의 콜스택 깊이를 갖게 됨 - O(log n)만큼의 스택
  • 왜? 기본 단계에 더 빨리 도달하기 때문.

✅ POINT : 퀵 정렬에서는 하위 배열로 나누기 위해 배열의 모든 원소를 기준 원소와 비교해야 한다

• 기준원소보다 작은지 큰지 판별해야 하기 때문
• O(n)만큼의 시간이 걸린다.
• 첫 단계 뿐 아니라 이후 모든 콜스택에서 이만큼 비교가 필요하다.
• 배열을 어떻게 분할하는지에 관계없이 모든 경우에 O(n)만큼의 시간이 걸린다.
• 최선의 경우
  • 각각의 콜스택마다 O(n)시간이 걸리고, 콜스택의 높이는 O(log n)이기 때문에,
  • 전체 알고리즘 실행시간은 O(n) x O(log n) = O(n log n) 이다.
• 최악의 경우
  • 각각의 콜스택마다 O(n)시간이 걸리고, 콜스택의 높이는 O(n)이기 때문에,
  • 전체 알고리즘 실행시간은 O(n) x O(n) = O(n제곱) 이다.
• 일반적인 경우
  • 최선의 경우와 같은 실행 속도를 가진다.
  • 기준 원소를 배열 내에서 무작위로 선택했을 때, 평균적으로 O(n log n)의 실행 속도를 가지기 때문.