퀵 정렬은 대표적인 분할 정복 알고리즘이다, 하지만 알고리즘이 수행되는 과정을 살펴보면 정복 후 분할하는 알고리즘이다.
피봇은 항상 요소의 가장 오른쪽 멤버가 되는 퀵정렬
1. 퀵 정렬의 아이디어는 피봇이라는 원소(숫자)를 정하고, 피봇보다 작은 숫자는 왼편으로, 피봇보다 큰 숫자는 오른편에 위치하도록하고, 피봇을 그 사이에 놓는다.
2. 피봇을 기준으로 작은쪽(왼쪽)과, 큰쪽(오른쪽)의 순서는 상관하지 않는다.
3. 피봇의 왼쪽엔 피봇으로 정한 수보다 작은수들만 모여있다. 순서X
4. 피봇 이전의 수를 기준으로 다시 수들을 정렬하고,
5. 피봇의 위치를 그 수들의 사이에 놓는다.
6. 1 ~ 5를 반복한다.
예)
7 2 5 1 3 4
피봇은 4가된다.
4보다 작은 애들을 왼쪽으로 몰아둔다.
j가 4보다 작을 경우 i와 자리를 바꾼다
p는 피봇
i, j | p | ||||
7 | 2 | 5 | 1 | 3 | 4 |
7은 4보다 크니 자리교환이 일어나지 않는다. / j 1증가
i | j | p | |||
7 | 2 | 5 | 1 | 3 | 4 |
2는 4보다 작으니 j와 i는 자리를 교환/ j, i 1씩증가
i | j | p | |||
2 | 7 | 5 | 1 | 3 | 4 |
5는 4보다 크니 자리교환 x / j 1증가
i | j | p | |||
2 | 7 | 5 | 1 | 3 | 4 |
1은 4보다 작으니 i와 자리교환 / j, i 1씩 증가
i | j | p | |||
2 | 1 | 5 | 7 | 3 | 4 |
3은 4보다 작으니 i와 j 자리교환/ j, i 1씩 증가
i | p j | ||||
2 | 1 | 3 | 7 | 5 | 4 |
j가 r에 도달했으니 i와 j 자리교환후 1회전 끝.
p | |||||
2 | 1 | 3 | 4 | 5 | 7 |
피봇의 위치가 i로 왔다.
좌 우의 정렬관계와는 상관없이 4보다 왼쪽은 적은멤버, 오른쪽은 큰멤버 -> 4의 위치는 정해졌다.
그런 다음 재귀호출을 한다. p - 1을 피봇으로 삼아 다시 정렬.
p | ||
2 | 1 | 3 |
2와 비교/ j 1 증가
j | p | |
2 | 1 | 3 |
1과 비교/ j 1증가
p j | ||
2 | 1 | 3 |
이번엔 위치를 바꿀 요소가 없다 그럼 다시 p - 1을 피봇삼아 다시 정렬
j | p |
2 | 1 |
이번엔 1보다 큰 2가 있으니 자리를 바꾼다.
p | j |
1 | 2 |
이제 요소가 1개만 남았으므로 조건에 부합되지 않아 호출되지 않는다.
이렇게 되면 0번부터 p - 1가 재귀호출 되지 않는다.
이제 p + 1부터 마지막까지가 재귀호출된다.
40 기준 왼쪽의 정렬을 끝내고 40기준 오른쪽 정렬을 시작한다.
왼쪽 정렬 결과)
1 | 2 | 3 | 4 | 5 | 7 |
오른쪽 정렬을 시작하게 되는데 오른쪽은 이미 정렬이 되어있다.
정렬이 되어있어도 한 개씩 계속 호출되서 정렬을 하는데
요소가 한개일 경우( left 인덱스와 right인덱스가 같을경우)에는 호출되지 않고 넘어간다.
void quicksort(int a[], int left, int right){
if (left < right) { //left인덱스보다 right인덱스가 클 경우
int pivot = partition(a, left, right); //partition실행 현재 pivot의 인덱스를 return함
quicksort(a, left, pivot - 1); //재귀호출로 피봇 위치의 -1까지 정렬 하므로 점점 왼쪽으로 정렬
quicksort(a, pivot + 1, right); //피봇위치의 +1 부터 마지막까지 점점 정렬
}
}
int partition(int a[], int left, int right){
int pivot = a[right]; //피봇은 넘겨받은 right요소
int i = left - 1; //i는 i-1로 시작하며 교환이 일어나야 할 때에만 증가함
for (int j = left; j <= right - 1; j++) { //right는 피봇이기 때문에 피봇 전까지 반복
if (a[j] <= pivot) {// pivot보다 작다면
i++; //i를 증가시키고
swap(a, i, j); //a배열에 i와 j의 위치를 바꾼다
}
}
swap(a, i + 1, right); //i는 현재까지 피봇보다 작은요소의 마지막을 가리킴 피봇은 마지막 요소 뒤에들어가야함
//i의 다음자리에 현 피봇을 넣는다
return (i + 1); //이 전줄에서 i + 1은 피봇의 위치라고 설명함.
}
시간복잡도
최선: O(N log N)
최악: O(N^2)