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

Quick sort

정의 : 재귀 호출을 이용한 대표적인 정렬

• 배열 중에 값 하나를 pivot으로 설정한다.

• pivot과 같거나 작은 값은 왼쪽 배열(left)에 그렇지 않은 값은 오른쪽 배열(right)에 저장한다.

• 이후, 왼쪽 배열과 오른쪽 배열을 각각 Quicksort를 진행해주면 위와 같이 정렬이 완료된다. 과정을 좀 더 자세히 보기 위해서 왼쪽의 배열 [4, 2, 2, 4, 3, 1]의 Quick Sort 과정을 살펴보자.

• 먼저, 값 하나를 pivot으로 설정해준다.

• 설정한 pivot을 기준으로 왼쪽에는 pivot보다 작거나 같은 값을 오른쪽에는 pivot보다 큰 값을 넣어준다.

• pivot을 설정해준다.

• pivot을 기준으로 pivot 보다 작거나 같은 값을 왼쪽에, 그렇지 않은 값을 오른쪽에 넣어준다.

• pivot을 설정해주고 마찬가지의 과정을 반복한다.

• 그렇게 되면, pivot만 남게 되는 상황이 온다. (데이터의 길이가 1인 경우) 그러면 자기자신만을 반환해준 상태로 재귀를 종료시키면, 재귀가 돌지 않은 흰색 부분부터 차례대로 돌게 된다.

• 즉, 위의 그림처럼 흰색의 2가 빨간색의 2로 재귀가 시작하게 되는 것이다.

• 마찬가지로, 흰색의 3과 4의 경우도 재귀가 들어가서 정렬이 되게 되고 남은 과정도 재귀 호출이 진행되면서 자연스럽게 정렬이 되게 된다.

코드

def getSmallElements(array, pivot) :
    '''
    array에서 pivot보다 작거나 같은 원소들을 list로 반환하는 함수
    그러므로 array와 pivot을 받아야한다.
    '''

    result = [] # 작거나 같은 원소들 담을 거임

    for i in array :
        if i <= pivot :
            result.append(i)

    return result

def getLargeElements(array, pivot) :
    '''
    array에서 pivot보다 큰 원소들을 list로 반환하는 함수
    그러므로 array와 pivot을 받아야한다.
    '''

    result = [] # 큰 원소들 담을 거임

    for i in array :
        if i > pivot :
            result.append(i)

    return result

def quickSort(array):
    '''
    퀵정렬을 통해 오름차순으로 정렬된 array를반환하는 함수를 작성하세요.
    '''
    '''
    1. pivot 잡는다 : array[0]
    2. pivot 보다 작거나 같은 원소들을 left에다가 대입
    3. pivot 보다 큰 원소들을 right에다가 대입
    4. left, right를 각각 정렬한다.
    5. left+pivot+right를 반환한다.
    '''
    # array에 아무것도 없거나 1개 있을 때 -> 정렬 완료
    if len(array) <= 1 :
        return array # 받은 거 그대로 반환

    pivot = array[0] # 1.

    '''
    [3,4,5,2,3,6,1,2,3,4] 에서 3이 pivot인데 정렬할 때, 맨 앞의 3은 빼고 들어가야 함.
    '''

    left  = getSmallElements(array[1:],pivot) # 2. 작거나 같은 element들 (pivot 빼고)
    right = getLargeElements(array[1:],pivot) # 3. 크거나 같은 element들 (pivot 빼고)

    left = quickSort(left) # 4.
    right = quickSort(right)
    # 쭉 내려가다보면 왼쪽이나 오른쪽에 원소가 하나 또는 없는 경우가 생기는데 이때 다 정렬되어있다.

    return left + [pivot] + right # 5.
    return array 

def main():
    line = [int(x) for x in input().split()]

    print(*quickSort(line))

if __name__ == "__main__":
    main()

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn