[Python] 퀵정렬 구현하기

 

 

quick sort

 

입력으로 n개의 수가 주어지면, quick sort를 구현하는 프로그램을 작성하세요.

 

 

입력 예시

10 2 3 4 5 6 9 7 8 1

 

출력 예시

1 2 3 4 5 6 7 8 9 10

 

---

 

 

 퀵정렬을 통해 오름차순으로 정렬된 array를 반환하는 함수를 작성하세요.

 

 

 

def quickSort(array):
    '''
    퀵정렬을 통해 오름차순으로 정렬된 array를 반환하는 함수를 작성하세요.
    '''
    
    
    # 1. 기저조건: array의 요소가 비어있거나 하나인 경우에는 array를 리턴합니다.
    
    if len(array) <= 1 :
        return array
    
    # 2. array의 맨 앞 값을 pivot으로 저장합니다.
    pivot = array[0]

    left = getSmall(array[1:], pivot)
    right = getLarge(array[1:], pivot)

	# 5. pivot을 기준으로 각각 왼쪽과 오른쪽에 정렬을 하고, quickSort를 적용하면 오름차순으로 정렬된 Array를 반환 
    return quickSort(left) + [pivot] + quickSort(right)

	# 3. getSmall 이라는 함수는 array에서 pivot보다 작거나 같은 값을 리스트로 담아 리턴합니다.
def getSmall(array, pivot) :
    data = []

    for a in array :
        if a <= pivot :
            data.append(a)
    return data

	# 4. getLarge 이라는 함수는 array에서 pivot보다 큰 값을 리스트로 담아 리턴합니다.
def getLarge(array, pivot) :
    data = []

    for a in array :
        if a > pivot :
            data.append(a)
    return data

return array 

def main():
    line = [int(x) for x in input("정렬할 수를 입력하세요 (예시:10 2 3 4 5 6 9 7 8 1): ").split()]

    print('정렬 결과:', *quickSort(line))

if __name__ == "__main__":
    main()