글 읽기 - python sort함수와 quick_sort 질문입니다.(11004)

fblood53 2년 전 0

위쪽은 내장함수를 이용했고 아래쪽은 퀵소트를 구현해보았습니다 퀵소트가 N이 너무 작지 않을때 가장 빠른 정렬 알고리즘으로 알고있었는데 시간 초과가 떠서 질문을 남깁니다 혹시 피벗선택의 방식이 이상해서 o(n^2) 이 되고있는 걸까요? 구현 방식에 문제가 있거나 효율적이지 못하다면 충고를 받고싶습니다.

# 정답 코드(내장 함수 사용)
N, K = map(int, input().split())
num_list = list(map(int, input().split()))

num_list.sort()

print(num_list[K - 1])

# 시간 초과 코드(퀵소트 구현)
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
test_case = list(map(int, input().split()))

def pivot(array, idx1, idx2, idx3):
    if array[idx1] > array[idx2]: array[idx1], array[idx2] = array[idx2], array[idx1]
    if array[idx2] > array[idx3]: array[idx2], array[idx3] = array[idx3], array[idx2]
    if array[idx1] > array[idx2]: array[idx1], array[idx2] = array[idx2], array[idx1]
    return idx2

def qsort(array, left, right):
        
    pr = right
    pl = left
    mid = pivot(array, pl, (pl + pr) // 2, pr)
    pc = array[mid]

    array[mid], array[pr - 1] = array[pr - 1], array[mid]
    pl += 1
    pr -= 2

    while pl <= pr:
        while array[pl] < pc: pl += 1
        while array[pr] > pc: pr -= 1
        if pl <= pr:
            array[pl], array[pr] = array[pr], array[pl]
            pl += 1
            pr -= 1
        
    if left < pr: qsort(array, left, pr)
    if pl < right: qsort(array, pl, right)

qsort(test_case, 0, N-1)
print(test_case[K - 1])

djm03178 2년 전 1

퀵소트는 매우 느린 정렬입니다. 평균적인 경우에만 빠를 뿐, 최악의 경우 O(N^2)이 되며 실질적으로는 버블소트보다도 못한 속도를 냅니다.

fblood53 2년 전 0

답변 감사합니다! 그렇다면 pivot 선택이 최적의 선택이라는 가정 하에 가장 빠르다는 것일까요? 실제로는 그런 경우는 거의 없다고 보면 될까요?

djm03178 2년 전 1

가장 빠르다는 말을 어디서 보신 건지 모르겠지만 일반적으로도 다른 NlogN 정렬들에 비해 그다지 빠르진 않습니다. 자바의 Arryas.sort 정도에서만 dual-pivot quicksort를 사용하기는 합니다.

fblood53 2년 전 0

넵 친절한 답변 감사합니다!

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

문제

문제

출처

ICPC

python sort함수와 quick_sort 질문입니다.(11004)

fblood53 2년 전 0

djm03178 2년 전 1

fblood53 2년 전 0

djm03178 2년 전 1

fblood53 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말