[백준] 24090번 파이썬 - 퀵 정렬 1

24090번: 알고리즘 수업 - 퀵 정렬 1

 

간단한 퀵정렬 문제.

재귀를 사용하기 때문에 pypy3으로 제출하였다.

 

※ sys.setrecursionlimit()

파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이다. 

따라서 위 코드 괄호 안에 내가 원하는 깊이를 미리 설정해두어야 재귀 오류가 발생하지 않는다.

코드

import sys
sys.setrecursionlimit(int(1e4)) 
input = sys.stdin.readline

def partition(array,start,end):
    global cnt
    pivot = array[end]
    i = start-1
    for j in range(start,end): 
        if array[j] <= pivot: 
            i +=1
            array[i], array[j] = array[j], array[i]
            cnt += 1
            if cnt == k:
                print(array[i],array[j])

    if i+1 != end:
        array[i+1], array[end] = array[end], array[i+1]
        cnt += 1
        if cnt == k:
            print(array[i+1],array[end])
    return i+1

def quickSort(array,start,end):
    if start >= end:
        return
    q = partition(array,start,end)
    quickSort(array,start,q-1)
    quickSort(array,q+1,end)


n,k = map(int,input().split())
array = list(map(int,input().split()))
cnt = 0

quickSort(array,0,n-1)

if cnt < k:
    print(-1)

 

[알고리즘] 퀵 정렬(quick sort)