퀵 정렬(Quick sort)

1. 퀵 정렬(quick sort) 이란?

• 정렬 알고리즘의 꽃
• 기준점(pivot 이라고 부름)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수 작성
• 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업 반복
• 함수는 왼쪽 + 기준점 + 오른쪽을 합쳐서 리턴함
• 대표적인 분할 정복 알고리즘

 

2. 어떻게 코드로 만들까?

 

연습 - 리스트를 리스트 슬라이싱(예 [:2])를 이용해서 세 개로 짤라 각 리스트 변수에 넣고 출력해보기

1. 피봇 선택 (보통 맨 앞에 있는 데이터 선택)
2. 분류 => 작은 데이터, pivot, 큰 데이터
3. pivot 선택, 분류하기 (데이터 수가 1개가 될 때까지)
4. 합치기 (return ...)

def qsort(list):	#pivot 선정 ~ 분류
	pivot = list[0]
    for n in range(1, len(list)):
    	if pivot > list[n] : left.append(list[n])
        else: right.append(list[n])
        
def qsort(list):	#데이터가 1개일 때 recursive call 적용 두번째 부터 pivot 기준 분류
	if len(list) <= 1:return list
    for n in range(1, len(list)):
    	if pivot > list[n]:left.append(list[n])
        else : right.append(list[n])
    return qsort(left) + [pivot] + qsort(right) # recursive call 적용

코드로 작성

def qsort(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])
    #pivot 그냥 쓰면 리스트와 숫자를 더하는 셈이라 리스트로 만들어 준것
    return qsort(left) + [pivot] + qsort(right) 

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

출력 : [22, 28, 52, 53, 58, 62, 64, 81, 89, 90]

 

파이썬 list comprehension 사용해서 작성해보기

def qsort(data):
    if len(data) <= 1:
        return data
    pivot = data[0]

    left = [item for item in data[1:] if pivot > item] # pivot보다 작은 item만 left에 넣기
    right = [item for item in data[1:] if pivot <= item]

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

 

4. 알고리즘 분석

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