퀵 정렬 알고리즘 개념

퀵 정렬은 분할 정복 알고리즘(문제를 더 작은 2개의 문제로 분리해서 해결한 후 결과를 모아서 원래 문제를 해결하는 방법)의 하나로 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)기사가 개발했다. 가장 자주 사용하는 정렬 알고리즘으로 빠른 수행 속도가 특징이다. 기본적인 퀵 정렬은 아래 3단계를 반복하며 정렬한다.

1. 기준(Pivot; 피벗) 요소 선택 — 주로 배열의 중간 요소를 기준으로함
2. 기준 요소보다 작은 요소는 왼쪽으로 이동, 기준 요소보다 큰 요소는 오른쪽으로 이동
3. 이동시킨 왼쪽 / 오른쪽 요소들에 대해 1~2번 작업 반복

구현

Basic Quick Sort

<aside> 💡 구현하기 쉽지만 항상 새로운 left / right 배열을 생성해 비교한 요소를 추가하므로 메모리 낭비 심함

</aside>

Not in place 방식 : 추가 메모리 공간 필요 / 입력값 클수록 메모리 낭비 심함 Stable 방식 : 중복 데이터 순서 안바꿈

진행 과정 분석

• 🔍️ Basic Quick Sort 정렬 과정 시뮬레이션 ⭐️

1. 기준(Pivot; 피벗) 요소 선택
2. 기준 요소보다 작은 요소는 left 배열에 추가, 기준 요소보다 큰 요소는 right 배열에 추가
3. 배열 길이가 1이 될때까지 left right 배열에 1~2번 작업 반복