📌 퀵 정렬
: 배열을 두 부분으로 나눈 후, 이 부분들을 다시 순환적으로 정렬함
- 분할 정복 방법을 적용함
✅ 분할 원소(pivot)
- 두 부분 배열로 나눌 때의 기준 원소
- 간단히 첫번째 원소를 분할 원소로 한다!
✅ 분할
- 왼쪽에서 오른쪽 방향으로 검색
- 분할 원소보다 큰 key를 찾음 - 오른쪽에서 왼쪽 방향으로 검색
- 분할 원소보다 작은 key를 찾음 - 양 방향의 포인터가 서로 만나게 되면 검색 종료됨
🔎
1. 분할 원소는 첫번째 원소로 정한다.
2. 포인터 1은 왼쪽에서 오른쪽으로 분할 원소보다 큰 값(40)을 찾는다.
3. 포인터 2는 오른쪽에서 왼쪽으로 분할 원소보다 작은 값(15)을 찾는다.
4. 찾은 두 개 값의 위치를 바꾼다.
5. 위의 과정을 반복한다.
6. 포인터 1과 2는 분할 원소보다 큰/작은 값을 찾다가 서로 교차가 일어나면 분할 원소보다 작은 값(10)을 분할 원소와 위치를 바꾼다.
7. 분할 원소(30) 기준으로 분할 원소(30)보다 작은 원소들만 위치하고 오른쪽은 분할 원소(30)보다 큰 원소들이 위치하게 된다.
8. 분할을 계속 한다.
9. 원소가 하나가 될때까지 정렬한다.
❗ 퀵 정렬 특징
- 속도가 빠름
- 추가 메모리 공간을 필요로 하지 않음[O(log n)만큼의 메모리를 필요로 함]
- 최악의 실행시간: O(n²)
- 최악의 경우: 이미 제 순서대로 정렬되어 있을 때나 역순으로 정렬되어 있을 때 - 최선 실행시간: T(n) = O(nlogn)
- 평균 실행시간: T(n) = O(nlogn)
- 불안정적
❗ 퀵 정렬의 공간 복잡도
- O(n)개의 메모리 필요
- 비순환적으로 하면 O(log n)이면 됨. 그닥 중요하진 않음 이렇게만 알고있자!_!
