11004: k번째 수 - 퀵정렬

https://m.blog.naver.com/rhdwn6580/222114900448

 

Hoare 분할에서는 왼쪽에서 피벗보다 큰 값과 오른쪽에서 피벗보다 작은 값을 찾아 서로 교환합니다. 왼쪽도 잘못된 값이고 오른쪽도 잘못된 값일때 둘을 교환하는 것입니다.

def partition(A, left, right): 
    low = left + 1
    high = right
    pivot = A[left]

    while low <= high:
        while low <= right and A[low] <= pivot:
            low += 1
        while high >= left and A[high] > pivot:
            high -= 1
        if low < high:
            A[low], A[high] = A[high], A[low]

    A[left], A[high] = A[high], A[left]
    return high  # 피벗의 최종 위치

 

Hoare partition algorithm의 목표는 [pivot 이하 값들] pivot [pivot 초과 값들] 이렇게 만드는 것입니다. pivot을 변경하며 반복하면 (퀵)정렬이 되는 것이지요.

따라서 low는 pivot보다 큰 값을 찾으려고 오른쪽으로 이동(A[low] <= pivot)하고 high는 pivot보다 작거나 같은 값을 찾으려고 왼쪽으로 이동합니다. (A[high] > pivot)

 

위 코드는 하나의 피벗(Pivot)을 기준으로 리스트를 두 부분으로 나누는 작업(분할;partition)을 합니다.

low >= high 인 상태에서도 swap을 해버리면 이미 완성된 분할이 오염됩니다.

따라서  low와 high가 교차되기 전에만 swap을 수행(if low < high: )합니다.

이렇게 하면 추가적인 메모리(데이터 구조)를 거의 사용하지 않고, 기존 자료 구조만을 직접 수정하여 문제를 해결하는 inplace 방식으로 문제를 해결할 수 있습니다.

 

마지막으로 pivot의 위치를 변경해주어야 합니다. ( A[left], A[high] = A[high], A[left])

[ pivot | ... pivot보다 작은 값들 ... | high | ... pivot보다큰 값들 ... ]

↓                                                       ↑

피벗은 이제 high 위치로 가야 함!

 

A[left]는 pivot의 진짜 위치이고, while high >= left and A[high] > pivot: 루프를 종료하면 high는 pivot보다 작거나 같은 값이 되기 때문에 A[left]와 A[high]를 swap합니다.

마지막으로 최종 pivot 위치를 반환합니다.(return high)

 

 

---

Quick Sort와 Quick Select의 차이

1) pivot의 위치
Quick Sort는 피봇을 중간(mid)로 두고 왼쪽 정렬과 오른쪽 정렬을 합니다.
Quick Select는 피봇을 첫번째 노드로 두고 한쪽 정렬(왼쪽)만 진행합니다.(Hoare partition)

2) 종료조건의 등호
Quick Sort는 정렬이 목표인 알고리즘입니다. left == right인 경우는 요소가 1개뿐이므로 정렬할 필요가 없습니다. left < right이 종료 조건입니다.
Quick Select는 k번째 작은 원소를 찾는 것이 목표인 알고리즘입니다. left == right == k라면, 정답인경우도 탐색해야 하므로 left <= right이 종료 조건입니다.

---

k번째 수 찾기

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

def partition(AList,left,right):
    pivot =AList[left] #값
    low =left+1 #인덱스
    high = right
    
    while low<=high:
        while low <= right and AList[low] <=pivot:
            low+=1
        while high>= left and AList[high] >pivot:
            high-=1
        if low < high:
            AList[low], AList[high] = AList[high],AList[low]
    
    AList[left],AList[high] = AList[high],AList[left]
    return high    

def quickselect(arr,left, right, iTarget):
    if left<=right:
        pivot = partition(arr, left, right) #인덱스
        if(pivot==iTarget):
            return arr[pivot]
        elif pivot > iTarget:
            return quickselect(arr,left, pivot-1, iTarget)
        else:
            return quickselect(arr,pivot+1,right, iTarget)
print(quickselect(AList,0,N-1,K-1)) #a번째 = a-1인덱스

 

---

문제

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

예제 입력 1 복사

5 2
4 1 2 3 5

예제 출력 1 복사

2

 

해당 문제는 퀵정렬로 처리하려면 다양한 예외 상황을 고려해야 합니다. 아래 티스토리를 참고해주세요.

 

https://dingx2-story.tistory.com/71

[11004] K번째 수 #파이썬 #백준 #퀵정렬

 

저는 내부적으로 퀵 정렬이 아닌 [Timsort(팀소트)] 라는 정렬 알고리즘을 사용하는 리스트의 sort() 메서드를 사용했습니다.

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

AList.sort()
print(AList[K-1])