알고리즘 - 퀵 정렬(Quick Sort)

퀵 정렬은 대표적인 분할 정복 알고리즘이다, 하지만 알고리즘이 수행되는 과정을 살펴보면 정복 후 분할하는 알고리즘이다.

피봇은 항상 요소의 가장 오른쪽 멤버가 되는 퀵정렬

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)