[알고리즘] # 4_1 퀵 정렬

** 퀵 정렬(Quick sort)

• 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수가 필요
• 각 왼쪽, 오른쪽은 재귀 호출을 통해 위 작업을 반복함
• 함수는 [왼쪽] + 기준점 + [오른쪽]을 리턴함

 

 

 

** 구현

---

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)

 

- 파이썬 list comprehension을 사용해서 더 깔끔하게 작성

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)

---

 

** 알고리즘 분석

• 일반적인 경우, 병합 정렬과 유사, 시간 복잡도는 O(n*logn)
  • left, right가 각각 거의 반씩 나눠질 경우
• 최악의 경우, 시간 복잡도는 O(n^2)
  • left, right 생성시 한쪽으로만 쏠리는 경우
  • 맨 처음 pivot이 가장 크거나 가장 작아, 모든 데이터를 비교하는 상황