quick sort

퀵 정렬 (Quick Sort)

1. 정의 👨‍🚀 퀵 정렬(Quick Sort)은 분할 정복 방법을 이용하는 정렬 알고리즘이다. 퀵 정렬은 피벗(Pivot)을 기준으로 분할과 정복이 이루어지게 된다. 퀵 정렬은 '피벗을 선택하는 방식'과 '재귀 또는 비재귀 방식'의 선택에 따라 다양한 구현 방법이 존재한다. 이번 글에서는 '왼쪽 피벗을 선택하는 방식'과 '재귀 방식'을 통한 퀵 정렬을 알아보도록 하자. 2. 동작 방식 🦸‍♂️ 기본적인 동작 방식은 아래와 같다. 배열에서 임의의 원소인 pivot을 선택한다. (해당 글에서는 배열에서 제일 왼쪽 원소를 pivot으로 선택한다.) pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로, pivot보다 큰 원소는 오른쪽에 오도록 배열을 배치한다. pivot을 기준으로 나누어진 왼쪽 배열과 ..