[정렬 알고리즘] 파이썬 퀵 정렬 구현

Borahm·2021년 5월 12일
0

정렬 알고리즘

목록 보기
4/5
post-thumbnail

퀵 정렬(Quick Sort)

전개

  • pivot(중심점)과 left 리스트, right 리스트를 활용하여 퀵 정렬을 구현할 수 있다.
  1. pivot을 설정한다.
    • 여기에서는 마지막 인덱스에 해당하는 원소를 pivot으로 설정하였다.
  2. pivot보다 작은 데이터는 left 리스트에 담고, 큰 데이터는 right 리스트에 담는다.
  3. left 리스트와 right 리스트 각각을 재귀적으로 정렬한 후, left 리스트, pivot, right 리스트 순으로 이어붙인다.
  4. 주의할 점: 재귀함수를 사용하므로 기저 조건이 필요하다.
    • 기저 조건: 리스트의 길이가 1일 때 리스트를 반환한다.

시간 복잡도

  • 평균적으로는 O(NlogN{NlogN})
  • 최악의 경우 O(N2{N^2})
  • 이유는 추후에 서술할 예정이다.

구현 코드

방법 1: 정렬 후 새 리스트 리턴

def quick_sorted(numbers):
    """오름차순 퀵 정렬을 실행합니다."""
    if len(numbers) <= 1:
        return numbers

    pivot = numbers[-1]
    left = [n for n in numbers[1:] if n < pivot]
    right = [n for n in numbers[1:] if n >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)


if __name__ == '__main__':
    numbers = [6, 5, 6, 4, 3, 2, 1]
    sorted_numbers = quick_sort(numbers)
    print(sorted_numbers)  # [1, 2, 3, 4, 5, 6, 6]

방법 2: 정렬 후 리턴 값 없음

def quick_sort_sub(numbers, start, end):
    """ 오름차순 퀵 정렬을 실행합니다. """
    # 종료 조건: 정렬대상이 한 개 이하이면 정렬할 필요가 없음
    if end - start <= 0:
        return

    pivot = numbers[end]
    i = start  # i: pivot과 같거나 더 큰 값이 될 수 있는 인덱스

    for j in range(start, end):
        if numbers[j] <= pivot:  # j: pivot과 같거나 더 작은 값이 될 수 있는 인덱스
            numbers[i], numbers[j] = numbers[j], numbers[i]
            i += 1
    numbers[i], numbers[end] = numbers[end], numbers[i]

    quick_sort_sub(numbers, start, i - 1)  # 기준 값보다 작은 그룹을 재귀 호출로 다시 정렬
    quick_sort_sub(numbers, i + 1, end)  # 기준 값보다 큰 그룹을 재귀 호출로 다시 정렬


def quick_sort(numbers):
    """ 오름차순 퀵 정렬을 호출합니다. """
    quick_sort_sub(numbers, 0, len(numbers) - 1)


if __name__ == '__main__':
    numbers = [6, 5, 6, 4, 3, 2, 1]

    quick_sort(numbers)

    print(numbers)

'''
출력 결과

[1, 2, 3, 4, 5, 6, 6]
'''

Ref

0개의 댓글