[ 퀵 정렬 ] 알고리즘

 

1.  개념 

     

       퀵 정렬 : 나열된 데이터 내에서 기준값을 지정하여 각각의 데이터를 기준값보다  큰 데이터, 작은 데이터로 분류하는 것을 반복하는 정렬 

       

       * 시간 복잡도 : O(n²)

 

       퀵 정렬 방법

       

        -  나열된 데이터 내에서 pivot(기준값)을 정한다

     

        -  pivot을 제외한 데이터 배열의 시작과 끝을 각각 start, end 로 정한다

 

       아래의 과정을 start와 end가 만날 때까지 반복한다.

        1 )  start < pivot  :  pivot보다 작은 값이 제시될 때까지 start를 오른쪽으로 한 칸씩 옮긴다 

 

        2 )  end > pivot. :  pivot보다 큰 값이 제시될 때까지 end를 왼쪽으로 한 칸씩 옮긴다

 

        3 ) start > end 가 되면(start값과 end 값이 엇갈리면) start와 end를 swap 해준다

 

        start 와 end가 만나면 pivot 과 start, end가 만난 곳을 swap해준다

 

        start와 end가 만났던 위치를 기준으로 배열을 두 개로 나눠 준다

 

        분리 집합 내에서 start, end, pivot을 재설정해준다

         

       위의 과정을 분리 집합의  개수가 1개 이하가 될 때까지 반복한다   

 

  

   

   

 

 

2.  문제 풀이

 

# 1  K번째 수 구하기 - 백준 11004번

https://www.acmicpc.net/problem/11004

11004번: K번째 수

 

import sys 
input = sys.stdin.readline 

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

def quickSort(S,E,K):
    global A
    if S < E :
        pivot = partition(S,E)
        
        # pivot이 K와 같다면 더이상 정렬할 필요 없음
        if pivot == K:
            return
        
        # pivot이 K보다 크면 왼쪽 배열만 정렬 
        elif K < pivot :
            quickSort(S,pivot-1,K)
            
        # pivot이 K보다 작으면 오른쪽 배열만 정렬
        else:
            quickSort(pivot+1,E,K)


## 데이터 swap 함수 ##
def swap(i,j):
    global A
    A[i],A[j] = A[j],A[i]


## pivot 구하는 함수 ##

def partition(S,E):
    global A
    
    # 데이터가 2개면 비교해서 정렬
    if S+1 == E:
        if A[S] > A[E]:
            swap(S,E)
        return E 
    
    # M : 가운데 값 - pivot으로 설정
    M = (S+E) // 2
    # 데이터 값의 이동을 편리하게 하기 위해 start와 pivot의 위치 swap
    swap(S,M)
    pivot = A[S]
    # i : start / j : end
    i = S + 1
    j = E 
    
    # start와 end가 만날 때까지
    while i <= j:
        
        # pivot보다 큰 값이 제시될 때까지 j(end) 왼쪽으로 한 칸씩 옮기기
        while pivot < A[j] and j > 0:
            j -= 1
        
        # pivot보다 작은 값이 제시될 때까지 i(start) 오른쪽으로 한 칸씩 옮기기
        while pivot > A[i] and i < len(A) - 1:
            i += 1
        
        # i와 j를 다 옮겼는데도 i<=j일 경우 아래 과정 수행
        if i <= j:
            swap(i,j)
            i += 1
            j -= 1
    
           
    A[S] = A[j]
    A[j] = pivot
    return j

quickSort(0,N-1,K-1)
print(A[K-1])