퀵정렬

퀵정렬은 시간복잡도가 log n 인 알고리즘입니다.

제가 사용하는 언어는 파이썬이고 구현은 파이썬의 리스트 슬라이싱 기능을 통해 재귀적으로 표현했습니다.

중간 값 pivot 값을 정하고 그 중간값을 기준으로 중간값 보다 크면 오른쪽 리스트에 작으면 왼쪽 리스트에 추가한다음 왼쪽과 오른쪽의 리스트가 계속 반씩 나뉘어져 정렬을 할 수 있도록 재귀적으로 구현했습니다.

 

---

 

def quicksort(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 quicksort(left) + [pivot] + quicksort(right) // 리턴값에 함수를 다시 호출해줘서 재귀호출 해줌

 

퀵정렬은 버블정렬과 같은 기본 정렬에 비해 시간 복잡도가 빨라 데이터를 많이 처리해야될때 유용하게 쓰일 수 있습니다.