알고리즘 : 퀵 정렬(Quick sort)

출처 : 위키백과

퀵 정렬(quick sort)은?

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

알고리즘 구현하기

• quicksort 함수 만들기
• 리스트 갯수가 한 개이면 해당 리스트 리턴, 아니라면 리스트 맨 앞의 데이터를 pivot(기준점)으로 놓기
• left, right리스트 변수를 만들고 맨 앞의 데이터를 뺀 나머지 데이터를 pivot과 비교
• 기준점보다 작으면 left.append(해당 데이터)
• 기준점보다 크면 right.append(해당 데이터)
• return quicksort(left) + pivot + quicksort(right)로 재귀호출

def quicksort(data):
	if len(data) <= 1:
    	return data
    left, right = list(), list()
    pivot = data[0]
    
    for index in range(1, len(data)):
    	if pivot > data[index]:
        	left.append(data[index])
        else:
        	right.append(data[index])
            
    return quicksort(left) + [pivot] + quicksort(right)
    
#리스트로 만들어서 리턴하기 : return quicksort(left) + [pivot] + quicksort(right)

import random

data_list = random.sample(range(100), 10)

quicksort(data_list)

 

알고리즘 분석

• 병합정렬과 유사함, 시간복잡도 O(n log n)
• 최악의 경우에는 맨 처음 pivot가 가장 크거나 가장 작으면 모든 데이터를 비교하는 상황이 나옴 O(n²)