알고리즘 - 퀵 정렬

퀵정렬이란?

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

알고리즘 구현

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

리스트로 만들어서 리턴하기: return quick_sort(left) + [pivot] + quick_sort(right)

코드

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])
    return qsort(left) + [pivot] + qsort(right)
    
import random

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

qsort(data_list)

실행결과

[7, 11, 13, 24, 26, 38, 41, 76, 78, 88]

List Comprehension 사용 코드

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

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

qsort(data_list)

실행결과

[0, 20, 26, 37, 39, 55, 58, 74, 85, 98]