[We-Co] 퀵정렬 (Quick sort)

안녕하세요. 위기의 코딩맨 입니다.

오늘은 퀵정렬에 대해서 알아보도록 하겠습니다.

 

[ 퀵정렬 ] 

말 그대로 빠르게 정렬하는 방식입니다.

기준 값을 설정하여, 그 값보다 작은 숫자, 큰 숫자를 서로 다른 배열로 저장합니다.

그 나눈 2개의 배열을 재귀함수로 나누는 과정을 반복하여 정렬하는 방식입니다.

 

[출처]https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

소스 코드를 확인해보겠습니다.

 

quickArray = [5, 1, 3, 2, 10]

 

def QuickSort(quickArray):
    if len(quickArray) < 2:
        return quickArray
    else:
        pivot = quickArray[0]
        list_1 = list(filter(lambda x: x < pivot, quickArray))
        list_2 = list(filter(lambda x: x > pivot, quickArray)) 
return QuickSort(list_1) + [pivot] + QuickSort(list_2)

 

확인해 보면 quickArray을 받는 QuickSort() 메서드를 만들고

 if len(quickArray) < 2: 은  전달받은 리스트가 1개면 전달받은 리스트를 반환하는 부분입니다.

또한, 재귀함수에서 마무리 되는 부분입니다.

다음 부분은 2개 이상으로 전달 받게 되면   pivot = quickArray[0]이 실행되는데,

전달 받은 리스트에서 첫번째 인자를 가져오는 부분입니다. 이 부분이 기준이 되는거죠~

 

그 기준으로 lambda의 reduce를 사용하여 해당 값보다 작은 값들, 큰 값들의 리스트를 만들어 냅니다.

그 리스트를 다시 재귀함수로 보내어 다시 이 과정을 리스트가 1개가 될때 까지 반복하여 정렬합니다.

그럼 정렬된 작은 값 + 기준 값 + 정렬된 큰 값 들이 모여서 반환 되는 코드입니다.

 

 

오늘은 간단하게 퀵정렬에 대해서 알아보았습니다.

천천히 하나하나 알아가며 기초를 쌓도록 합시다!