[TIL] 퀵정렬 - Quick Sort

퀵정렬

• 기준점(pivot)을 정해서 기준점보다 작은 데이터를 왼쪽, 큰 데이터를 오른쪽으로 옮긴다.
• 옮겨진 왼쪽, 오른쪽 리스트는 재귀용법을 사용하여 다시 동일한 작업을 반복한다.
• 결과값은 왼쪽+기준점+오른쪽

def quickSort(data):
    if len(data) <=1:
        return data

    left,right = list(),list()
    pivot = data[0]

    for i in range(1, len(data)):
        if pivot > data[i]:
            left.append(data[i])
        else:
            right.append(data[i])

    return quickSort(left)+[pivot]+quickSort(right)

 

파이썬의 list comprehension을 사용하면 더 쉬운 코드로 작성 가능하다.

def quickSort(data):
	if len(data) <=1:
    	return data

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

 

퀵정렬의 시간복잡도?
-O(nlogn)
-최악의 경우(pivot이 가장 크거나 작은 경우) 모든 데이터를 비교해야 하므로 O(n*n)