Hello Coding 그림으로 개념을 이해하는 알고리즘 Study Note 04

Chapter 4 퀵 정렬 (Quick Sort)

분할 정복 (Divide and conquer)

- 분할 : 주어진 문제를 더 작은 크기의 동일한 문제로 분할

- 정복 : 분할된 각각의 작은 문제를 재귀적으로 해결

- 결합 : 분할된 문제의 해결책을 합쳐 원래 문제의 해결책을 얻음

장점

- 복잡한 문제를 간단한 문제로 나누어 해결

- 재귀적 구현을 통해 간결하게 구현할 수 있음

- 분할된 문제들을 병렬 처리할 수 있어 성능 향상에 도움

단점

- 재귀 호출에 따른 오버 헤드가 발생 할 수 있음

- 문제를 분할하는 과정에서 분할 비용이 발생할 수 있음

- 분할된 해결책을 합치는 과정에서 결합 비용이 발생할 수 있음

예시

- 퀵 정렬, 합병 정렬, 이진 탐색, 최대 공약수 구하기(유클리드 호체법)

유클리드 호제법 (Euclid's algorithm), 최대 공약수 (Greatest Common Divisor, GCD)

- 두 개의 자연수의 최대공약수를 구하는 가장 효율적인 알고리즘 중 하나

- 큰 수를 작은 수로 나눈 나머지를 구함

- 나누는 수를 나머지로 바꾸고 나머지를 새로운 나누는 수로 하여 이전 과정 반복

- 나머지가 0이 되면 마지막으로 나눈 수가 최대공약수가 된다

퀵 정렬 (Quicksort)

- 분할 정복 알고리즘의 대표적인 예시로, 평균적으로 매우 빠른 정렬 속도를 자랑하는 정렬 알고리즘

- 최악의 경우 시간 복잡도 O(n^2), 평균 O(n log n)

원리

- 피벗 선택 : 정렬할 배열에서 임의의 값 하나를 피벗(pivot)으로 선택

- 분할 : 피벗을 기준으로 배열을 두 부분으로 나눔(큰 값은 왼쪽, 작은 값은 오른쪽)

- 재귀 호출 : 분할된 두 부분에 대해 각각 퀵 정렬을 재귀적으로 호출

- 결합 : 분할된 부분들이 정렬되면 전체 배열이 정렬된 상태가 됨

04_quicksort.py 작성 + 테스트

def quicksort(array):

    # 기본단계 원소의 개수가 0이나 1이면 이미 정렬되어 있다

    if len(array) < 2:

        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]))

Chapter 4 정리

분할 정복은 문제를 더 작은 조각으로 나누어 푸는 방법

대표적 예로 유클리드 호제법, 최대공약수 구하기, 퀵 정렬

퀵 정렬은 빠른 속도를 자랑하는 정렬 알고리즘

퀵 정렬은 평균적으로 O(n log n), 최악의 경우 O(n^2) 시간 복잡도를 가진다

빅오 표기법에서 상수항이 중요할 때는 서로 비슷한 시간 복잡도를 가진경우 ex) 퀵 정렬과 병합 정렬