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

퀵 정렬 이란?

• 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모으는 함수를 작성
• 각 왼쪽(left), 오른쪽(right)은 재귀용법으로 다시 동일 함수를 호출하여 반복함
• 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 return

 

파이썬 코드 구현

def qsort(data):
	if len(data) <= 1:
    	return data
    
    pivot = data[0]
    
    left = [ item for item in data[1:] if pivot > item ]
    right = [ item for item in data[1:] if pivot <= item ]
    
    return qsort(left) + [pivot] + qsort(right)