Sorting - (5)

Quick Sort

pivot 을 정해 해당 값보다 작은 데이터와 큰 데이터로 분류하여 recursive 하게 정렬하는 알고리즘
=Divide and conquer
시간복잡도가 일반적으로 O(nlogn)이지만 최악의 경우 O(n^2)

start, end 2개의 포인터가 있어 pivot 기준 start 쪽 데이터가 더 작으면 오른쪽으로 한 칸씩 이동하고 end 쪽 데이터가 더 크면 왼쪽으로 한 칸씩 이동한다.
만약 만약 둘 중 하나라도 차이가 난다면 swap을 한다.
start=end가 되면 start+1에 해당하는 데이터와 pivot을 서로 바꾼다.
이 후 recursive 하게 진행하면 된다.

코드를 통해 이해하는 것이 가장 좋을 것이다.

K번째 수 구하기(백준 11004번, 시간 제한: 2초)

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

입력
첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.
둘째에는 A1, A2, ..., AN이 주어진다. (-10^9 ≤ Ai ≤ 10^9)

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

입력 예시
5 2
4 1 2 3 5

출력 예시
2

코드 예시

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
A=list(map(int,input().split()))
def quickSort(start,end,k): #k 번째 수가 pivot 이면 더이상 구할 필요가 없다. 불필요한 sorting 안함.
    global A
    if start<end:
        pivot=partition(start,end) #pivot은 index이다. 
        if pivot==k:
            return
        elif k<pivot: #k가 pivot보다 작으면 왼쪽 그룹만 정렬하면 된다. 
            quickSort(start,pivot-1,k)
        else :
            quickSort(pivot+1,end,k)
def swap(i,j):
    global A
    temp=A[i]
    A[i]=A[j]
    A[j]=temp
def partition(start,end):
    global A
    if start+1==end: #data 가 2개일 경우
        if A[start]>A[end]:
            swap(start,end)
        return end
    M=(start+end)//2 #중간 index를 pivot으로 고른다
    swap(start,M) # pivot에 해당하는 값을 가장 앞으로 옮긴다
    pivot=A[start]
    i=start+1 # pivot이 start 자리를 이미 차지했음
    j=end 
    while i<=j:
        while pivot<A[j] and j>0: # j를 먼저 끝까지 찾아가본다  j를 기준으로 문제를 풀었음.
            j=j-1
        while pivot>A[i] and i<len(A)-1:
            i=i+1
        if i<=j:
            swap(i,j)
            i=i+1
            j=j-1
    A[start]=A[j]
    A[j]=pivot #pivot과 자리 바꾸기
    return j
quickSort(0,n-1,k-1) #k-1 이 원하는 index 위치
print(A[k-1]) 

int partition(int A[], int start, int end)
{
    int pivot = A[end];
    int index = start - 1;
    for (int i = start; i < end; i++)
    {
        if (A[i] <= pivot)
        {
            index++;
            int temp = A[i];
            A[i] = A[index];
            A[index] = temp;
        }
    }
    index++;
    int temp = A[end];
    A[end] = A[index];
    A[index] = temp;
    return index;
}

void quick_sort(int A[], int start, int end)
{
    if (start < end)
    {
        int q = partition(A, start, end);
        quick_sort(A, start, q - 1);
        quick_sort(A, q + 1, end);
    }
}

c 언어를 이용해서 풀었던 것과 비교도 한번 해보자.
partition 구하는 방법은 여러가지가 있기 때문에 정답은 없는 듯 하다!!