가장 빠른 정렬 알고리즘 중의 하나 퀵 이라는 이름 역시 정렬 속도가 매우 빠르다는 점에서 착안 - 교제 224p

✔️ 퀵 정렬 살펴보기

• 피벗 : 그룹을 나누는 기준
• 피벗을 기준으로 그룹을 나눠 각각의 그룹에 값이 1개씩만 들어가면 정렬 종료
• 이미지

✔️ 배열을 두 그룹으로 나누기

1. 피벗이 될 요소를 선택한다.

2. 피벗보다 작은 요소와 큰 요소로 나눠 그룹으로 묶는다.

3. 배열의 수가 홀수개인 경우에, 동일한 요소(피벗)을 교환하는 시도가 생긴다.

    → 이 의미 없어보이는 시도가 매번 이뤄져야하는
        양 끝에서 움직이는 인덱스의 위치가 서로 동일한 위치인지에 대한 검사를 없애준다.
   

✔️ 피벗을 기준으로 배열 나누기

• 코드
• 설명

✔️ 퀵 정렬

• 피벗을 기준으로 배열을 나누는 것을 반복하면 퀵 정렬이 된다
• 나누려는 배열에 값이 1개라면 나누지 않아도 된다.
• 재귀를 이용한 퀵 정렬
• 비재귀적 퀵 정렬

✔️ 스택의 용량

• 요소의 개수가 적은 배열일수록 적은 횟수로 분할을 종료
• 스택에 넣고 꺼내는 횟수는 같지만, 스택에 쌓이는 데이터의 최대 개수는 다르다.
• int arr = {6, 5, 4, 2, 7, 3, 1, 8}
• 그림 예시

1. 요소의 개수가 많은 그룹을 먼저 푸시하는 경우
   • 그림 예시
2. 요소의 개수가 적은 그룹을 먼저 푸시하는 경우
   • 그림 예시

✔️ 피벗 선택하기

• 빠른 정렬을 원한다면 배열을 정렬한 다음에 가운데 값을 피벗으로 하면 된다.

                     → 배열의 크기가 균등하게 나눠지기 때문
  

• 가운데 값을 구하고자 할 경우 그에 대한 처리가 필요하다.

                     → 이 처리에 대해 많은 계산 시간이 요구되어 배보다 배꼽이 커진다
  
                     → 1. 나눌 배열의 요소 개수가 3 이상이면 임의로 요소 3을 선택하고
                             그중에서 중앙값인 요소를 피벗으로 선택한다.
  
               → 2. 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서
                       두 번째 요소를 교환한다.
                       피벗으로 끝에서 두 번째 요소 값(arr[right-1])을 선택하여 나눌 대상의
                       범위를 (arr[left+1]) ~ (arr[right-2])로 좁힌다.
  

✔️ 시간 복잡도

• 배열을 조금씩 나누어 보다 작은 문제를 해결하는 과정을 반복
• $O(nlogn)$
• 정렬할 배열의 초기값이나 피벗의 선택 방법에 따라 시간 복잡도가 증가할 수 있다
• 예를들어 매번 단 하나의 요소와 나머지 요소로 나뉘면 n번의 분할이 필요
• 이러한 경우 $O(n^2)$의 시간 복잡도를 가지며 최악의 경우라고 볼 수 있다.

✔️ 연습문제

• Q10 : static void quickSort(int[] a, int n); 구현하기. n은 요소의 개수
• Q11 : 비재귀 퀵 정렬 푸시, 팝, 분할과정 출력하기
• Q12 : 요소의 개수가 적은 그룹을 먼저 나누는 메소드로 수정하기
• Q13 : 12번의 두 코드를 나눈 그룹의 요소 개수가 9 이하면 단순 삽입 정렬로 하기
• Q14 : 피벗 선택하기의 방법 1을 사용해서 13번 문제를 수정하자
• Q15 : 피벗 선택하기의 방법 2을 사용해서 13번 문제를 수정하자

✔️ 연습문제 정답

• Q10 : static void quickSort(int[] a, int n); 구현하기. n은 요소의 개수
• Q11 : 비재귀 퀵 정렬 푸시, 팝, 분할과정 출력하기
• Q12 : 요소의 개수가 적은 그룹을 먼저 나누는 메소드로 수정하기
• Q13 : 12번의 두 코드를 나눈 그룹의 요소 개수가 9 이하면 단순 삽입 정렬로 하기
• Q14 : 피벗 선택하기의 방법 1을 사용해서 13번 문제를 수정하자
• Q15 : 피벗 선택하기의 방법 2을 사용해서 13번 문제를 수정하자