[알고리즘] 퀵 정렬 (Quick Sort) 개념 정리 및 코드 리뷰

감자 코딩에 감자개발자입니다. 이번시간에 살펴볼 개념은 Quick sort  퀵정렬입니다.

1. 퀵정렬의 특징

1) 불안정한 정렬

2) 다른원소와 비교했을때 "비교 정렬"이라 칭합니다.

3) 매우 빠른정렬방식

4) 분할정복 방식(divide and conquer) -큰 문제를 작은문제 1,2로 분할하는 방식

5)  시간복잡도 O(nlogN)

2. 퀵정렬 과정

1) 리스트 하나의 요소 Selection "pivot"

2) 피벗 기준으로 피벗보다 작으면 "왼쪽"

3) 피벗 기준으로 피벗보다 크면 "오른쪽"

4) 피벗 제외한 왼쪽/오른쪽 리스트 다시 재정렬(순환호출)

5) 부분 리스트들이 더이상 분할 불가능할때까지 반복한다.