[정렬]퀵 정렬

퀵 정렬

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

 

아래 이미지처럼, 피벗을 기준으로 그룹을 나눠 각각의 그룹에 값이 1개씩만 들어가면 정렬이 종료된다. 
* 피벗: 그룹을 나누는 기준

그림출처: https://www.podo-dev.com/blogs/75

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

1. 피벗이 될 요소를 선택한다.
2. 피벗보다 작은 요소와 큰 요소로 나눠 그룹으로 묶는다.
3. 배열의 수가 홀수개인 경우에, 동일한 요소(피벗)을 교환하는 시도가 생긴다.
   → 이 의미 없어보이는 시도가 매번 이뤄져야하는 양 끝에서 움직이는 인덱스의 위치가 서로 동일한 위치인지에 대한 검사를 없애준다.

 

✔️ 스택의 용량

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

그림 출처 : Do it 자료구조 알고리즘[자바편] 교재 287p

 

✔️ 피벗 선택하기

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

 

✔️ 시간 복잡도

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

 

자료출처:www.notion.so/52a65eeb5d1c4379a0da737ed8d4bc98