'퀵'하게 정렬한다고? 빠르고 똑똑한 정렬 알고리즘, 퀵 정렬(Quick Sort)!🏎️

안녕하세요 logro 입니다 :)

오늘은 정렬 알고리즘 중에서도 특히 빠르고 효율적이라고 소문난 퀵 정렬(Quick Sort)에 대해 알아볼게요! 이름부터가 뭔가 멋지죠? 😎

---

🍰 퀵 정렬, 케이크 자르기처럼 생각해보자!

퀵 정렬을 한마디로 설명하면 “기준점을 정해서 좌우로 나누고, 그걸 반복해서 정렬하는 방식”이에요.

조금 더 쉽게 설명해볼게요. 🎂

생일 케이크를 친구들과 나누고 싶어요!
가장 좋아하는 조각(기준점, Pivot)을 고른 뒤, 그보다 작거나 덜 달면 왼쪽에,
더 크거나 더 달면 오른쪽에 두고, 각 그룹을 다시 같은 방식으로 나눠요!

 

이걸 코드로 옮기면 퀵 정렬이 됩니다.
즉, 기준점(Pivot)을 기준으로 좌우를 나누고, 그걸 계속 반복해 정렬하는 거예요.

---

💻 퀵 정렬 예시

 

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # 재귀 종료 조건

    pivot = arr[0]  # 첫 번째 요소를 기준점으로 선택
    left = [x for x in arr[1:] if x <= pivot]  # pivot보다 작거나 같은 값들
    right = [x for x in arr[1:] if x > pivot]  # pivot보다 큰 값들

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

# 사용 예시
data = [5, 3, 8, 4, 2, 7, 1, 10]
print(quick_sort(data))

---

🔍 왜 퀵 정렬이 빠를까?

퀵 정렬은 평균적으로 O(n log n) 의 시간복잡도를 가져요.
즉, 데이터를 반으로 쪼개면서 정렬하기 때문에 전체를 일일이 비교하지 않아도 빠르게 끝납니다.

하지만!
최악의 경우(이미 정렬된 배열을 기준점이 계속 못 고르면)에는 O(n²) 이 될 수도 있어요.

그럼에도 불구하고 실제 사용에선 매우 빠르고 효율적이기 때문에 많이 쓰인답니다 🙂

---

✅ 정리해볼까요?

• 퀵 정렬은 분할 정복(divide and conquer) 알고리즘의 대표 주자!
• 기준점을 잡고, 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누며 정렬.
• 재귀적으로 나눠 정렬하므로 코드도 깔끔하고 이해도 쉬움.
• 평균적으로 매우 빠른 정렬 방법 (O(n log n))

---

다음에 다른 정렬 알고리즘과의 차이점도 비교해보면 재미있을 거예요 😉
이해 안 가는 부분이나 추가로 궁금한 주제가 있다면 언제든지 말해주세요!