본문으로 건너뛰기
실습하기

퀵 정렬(Quick Sort)이란?

퀵 정렬은 피벗(pivot)을 사용하여 배열을 두 부분으로 나누고, 각 부분을 재귀적으로 정렬하는 방식으로 작동하는 정렬 알고리즘입니다.


키워드​

  • 피벗: 배열을 분할하는 기준이 되는 요소입니다.

  • 분할: 피벗을 기준으로 배열을 두 부분으로 나눕니다.

  • 정복: 분할된 각 부분을 개별적으로 정렬합니다.

  • 최악 시간 복잡도: O(n^2) - 배열이 이미 역순일 때 발생합니다.

  • 평균 시간 복잡도: O(n log n) - 대부분의 경우, 퀵 정렬은 로그 선형 시간 복잡도를 가집니다.


퀵 정렬의 단계별 과정​

  1. 피벗 선택: 배열에서 하나의 요소(피벗)를 선택합니다.

  2. 분할: 피벗을 기준으로 배열을 두 부분으로 나눕니다. 이때, 피벗보다 작은 요소는 피벗의 왼쪽, 큰 요소는 오른쪽에 배치됩니다.

  3. 재귀적 정렬: 분할된 각 부분을 재귀적으로 다시 퀵 정렬합니다.

  4. 병합 단계: 정렬된 부분 배열들을 병합합니다. 퀵 정렬에서는 실제로 병합 과정이 없지만, 재귀적으로 정렬된 부분들이 결합되어 전체 배열이 정렬됩니다.

  5. 정렬 완료: 모든 부분 배열이 정렬되어 완전히 정렬된 배열이 됩니다.


퀵 정렬의 특징​

  • 비안정 정렬: 퀵 정렬은 동일한 값을 가진 원소의 상대적 순서가 변경될 수 있는 비안정적인 정렬 방법입니다.

  • 메모리 최적화: 추가적인 메모리를 거의 사용하지 않고, 원래의 배열 내에서 정렬을 수행합니다.

  • 효율적인 평균 성능: 대부분의 실제 상황에서 퀵 정렬은 매우 빠르며, 평균적으로 O(nlog n)의 시간 복잡도를 갖습니다.

  • 피벗 선택 중요성: 피벗 선택은 퀵 정렬의 성능에 큰 영향을 미칩니다. 일반적으로 중간값이나 무작위 요소가 피벗으로 좋은 선택입니다.


퀵 정렬의 장단점​

  • 장점: 대규모 데이터에 대한 높은 효율성, 추가 메모리 사용이 거의 없음.

  • 단점: 최악의 경우 O(n^2)의 시간 복잡도와 비안정성

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!