dogeonLog
🌙
💻코딩테스트

[이코테_코딩테스트] 정렬 알고리즘 - 퀵 정렬 (Quick Sort)

date
Jul 27, 2023
slug
coding-test-quick-sort
author
status
Public
tags
Python
코딩테스트
summary
퀵 정렬을 알아보자
type
Post
thumbnail
Untitled (1).png
category
💻코딩테스트
updatedAt
Jul 26, 2023 05:48 PM

퀵 정렬 (Quick Sort)

  • 기준 데이터(Pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
  • 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
  • 병합 정렬(Merge Sort)와 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
  • 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.
 

퀵 정렬 동작 예시

[Step 0] 현재 피벗의 값은 ‘5’, 왼쪽에서부터 ‘5’보다 큰 데이터를 선택하므로 ‘7’ 선택, 오른쪽에서부터 ‘5’보다 작은 데이터를 선택하므로 ‘4’ 선택 → 두 데이터의 위치 변경

notion image
 

[Step 1] 현재 피벗의 값은 ‘5’, 왼쪽에서부터 ‘5’보다 큰 데이터를 선택하므로 ‘9’ 선택, 오른쪽에서부터 ‘5’보다 작은 데이터를 선택하므로 ‘2’ 선택 → 두 데이터의 위치 변경

notion image
 

[Step 2] 현재 피벗의 값은 ‘5’, 왼쪽에서부터 ‘5’보다 큰 데이터를 선택하므로 ‘6’ 선택, 오른쪽에서부터 ‘5’보다 작은 데이터를 선택하므로 ‘1’ 선택

  • 아래 사진처럼 위치(화살표)가 엇갈리는 경우 피벗(Pivot)과 ‘작은 데이터’의 위치 변경
notion image
 

[분할 완료] ‘5’ 기준으로 왼쪽 데이터는 모두 ‘5’보다 작고, 오른쪽에 있는 데이터는 모두 ‘5’보다 크다.

  • 이렇게 피벗(Pivot)을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide)라고 한다.
notion image
 

[왼쪽 데이터 묶음 정렬] 왼쪽에 있는 데이터에 대해 위 과정처럼 정렬 수행

notion image

[오른쪽 데이터 묶음 정렬] 오른쪽에 있는 데이터에 대해 위 과정처럼 정렬 수행

notion image
 

퀵 정렬이 빠른 이유 - 직관적인 이해

  • 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 기대할 수 있음
    • 너비 X 높이 =
notion image
 

퀵 정렬의 시간 복잡도

  • 퀵 정렬은 평균의 경우 의 시간 복잡도를 가진다.
  • 최악의 경우 의 시간 복잡도를 가진다.
      • 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열이라면?
      notion image
      • ‘0’보다 큰 데이터 선택 ‘1’, 작은 데이터 선택할 때 ‘1’과 교차
      • ‘0’ 자기 자신의 위치와 변경 후 분할
      • 왼쪽 데이터 묶음 정렬은 없고, 오른쪽 데이터 묶음 정렬은 ‘1’부터 ‘9’까지
      • 위 과정 반복
       
 

퀵 정렬 소스코드 - 일반적인 방식 (Python)

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: # 원소가 한 개인 경우
        return
    
    pivot = start
    left = start + 1
    right = end

    while(left <= right):
        while(left <= end and array[left] <= array[pivot]): # 피벗보다 큰 값 찾기
            left += 1
        while(right > start and array[right] >= array[pivot]): # 피벗보다 작은 값 찾기
            right -= 1
        
        if left > right:    # 위치 엇갈린 경우 -> 피벗과 피벗보다 작은 값의 위치 변경
            array[right], array[pivot] = array[pivot], array[right]
        else:   # 위치 안엇갈린 경우 -> 피벗보다 작은 값, 피벗보다 큰 값 위치 변경
            array[left], array[right] = array[right], array[left]
    
    # 분할 이후 왼쪽 묶음과 오른쪽 묶음 각각 정렬
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)
 

퀵 정렬 소스코드 - 파이썬의 장점을 살린 방식

  • 리스트 슬라이싱 + 리스트 컴프리헨션 사용
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    tail = array[1:]

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 묶음
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 묶음

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))
 
 
이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 4. 정렬 알고리즘” 영상을 보고 작성하였습니다.