글 읽기 - 파이썬3 퀵정렬 런타임에러 질문

vrdhan212 2년 전 0

이 문제를 처음 봤을 때

숫자 카드를 퀵정렬로 정렬한 뒤,

이진 탐색으로 해결하려했습니다.

정렬할 때 pivot은 가장 마지막 인덱스로 설정했습니다.

그런데, 런타임에러(RecursionError) 오류가 나버립니다.

재귀함수가 너무 많이 호출되서 에러가 나는건가요?

문제없이 퀵정렬하려면 어떻게 해야 할까요?

import sys
def qsort(num_list: list) -> list:
    n = len(num_list)

    if n <= 1:
        return num_list

    pivot = num_list[-1]
    left_list = []
    right_list = []
    for i in range(n - 1):
        if num_list[i] < pivot:
            left_list.append(num_list[i])
        else:
            right_list.append(num_list[i])
    return qsort(left_list) + [pivot] + qsort(right_list)


def binary_search(num_list: list, num: int) -> bool:
    left = 0
    right = len(num_list) - 1
    while left <= right:
        mid = (left + right) // 2
        if num_list[mid] == num:
            return True
        elif num_list[mid] > num:
            right = mid - 1
        else:
            left = mid + 1
    return False



n = int(input())
number_list = list(map(int, sys.stdin.readline().rstrip().split()))
number_list = qsort(number_list)
m = int(input())
check_list = list(map(int, sys.stdin.readline().rstrip().split()))
res = []
for k in check_list:
    if binary_search(number_list, k):
        res.append(1)
    else:
        res.append(0)
for p in res:
    print(p, end=' ')

circlezer0 2년 전 0

글쓴이님의 퀵소트는 무조건 맨 뒤의 원소를 pivot으로 설정하였기 때문에

[10,9,8,7,6,5,4,3,2,1]과 같이 입력이 오름차순 또는 내림차순으로 정렬이 되어 있는 경우 정렬 시간 증가와 함께 함수의 깊이가 입력된 수의 개수만큼 깊어집니다.

이를 방지하기 위해 pivot은 배열의 원소 중 무작위를 선택해야 합니다.

vrdhan212 2년 전 0

답변 감사드립니다 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬3 퀵정렬 런타임에러 질문

vrdhan212 2년 전 0

circlezer0 2년 전 0

vrdhan212 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말