퀵 정렬

퀵정렬 기본 원리

한 원소를 무작위로 골라 기준(Pivot)으로 삼고 배열을 분할한다.

선택한 원소보다 작은건 앞쪽으로 큰것은 뒤쪽으로 보낸다.

퀵 정렬은 분할정복 기법을 사용한다.

피벗 A를 정한후, 왼쪽에는 피벗보다 작은값을, 오른쪽에는 피벗보다 큰 값을 둔다.

피벗 A의 왼쪽값에 대해 또 피벗B를 정해 왼쪽값에는 피벗B보다 작은 값을 오른쪽에는 피벗보다 큰 값을 둔다.

피벗 A의 오른쪽값에 대해 또 피벗C을 정해 왼쪽값에는 피벗C보다 작은 값을 오른쪽에는 피벗보다 큰 값을 둔다.

이 순회를 반복한다.

분할정복

퀵정렬 time complexity

성능이 가장 좋을때 : 피벗을 중심으로 N/2개씩 분할반복 되었을때 

이 경우 log2N단계가 생성 최대 N번의 비교연산을 한다. 

따라서 평균 복잡도는 O(N log2N)이다.

 

 But 성능이 가장 안좋을때(정렬이 역순으로 되어있고 피벗을 0번째로 잡은경우)

N개의 단계를 N번 비교...
최악은 O(N^2)이다.

 

백준 수정렬 문제 _퀵정렬

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline



def Qsort(a:list,lt, rt):
    pl =lt
    pr = rt
    x = nums[(lt+rt)//2] #Pivot

    while pl<=pr: # pl 이 pr보다 커지거나 같아질 떄는 피벗을 기준으로 정렬이 끝났음을 의미
        while a[pl] < x :
            pl+=1
        while a[pr] > x :
            pr-=1
        if pl<=pr:
            a[pl],a[pr]=a[pr],a[pl]  #pr 은  피벗보다 작아지면서 끝났을것이고 pl 은 피벗보다 커지면서 끝났을것이다.
            pl+=1 #피벗보다 작은값이 기존 pl에 들어갔으므로 그 다음 인덱스로 검색
            pr-=1

    if lt<pr : Qsort(a,lt,pr)  #피벗을 기준 왼쪽과 오른쪽을 똑같이 또 정렬반복
    if pl < rt : Qsort(a,pl,rt)


n = int(input())
nums = list(int(input()) for _ in range(n))

Qsort(nums,0,n-1) #퀵정렬을 이용 정렬
for i in nums:
    print(i)