퀵 정렬(quick sort)

<특징>

1. 분할 정복 알고리즘

2. 평균적으로 매우 빠른 성능

3. stable 하지 않다

* stable 정렬: 정렬을 할 때 중복된 값들의 순서가 변하지 않는 정렬

--> 즉 퀵 정렬은 중복된 키도 비교함.(중복된 키들을 정렬할 때는 사용하지 않는 게 바람직함)

4. 시간복잡도 - 최악: O(n^2) 

                         평균:O(nlogn)

5. 공간복잡도 - O(nlogn)

in-place 정렬이라고 하기 힘들지만,  상대적으로 작은 메모리만을 사용하므로 흔히 in-place 정렬이라고 한다.

* in-place 정렬: 추가적인 메모리 공간이 거의 안드는 정렬

---

<원리>

위와 같은 배열을 오름차순으로 퀵 정렬 한다고 하자. 가장 먼저 pivot을 설정해야 하는데, pivot을 설정하는 것에는 여러가지 방법이 있다. 가장 앞의 원소, 중간 원소, 혹은 가장 뒤의 원소를 택하는 등의 방법이 있는데 여기서는 중간 원소를 pivot값으로 설정.

• 중간 값을 pivot으로 설정했다면 가장 왼쪽의 값을 left, 오른쪽의 값을 right로 잡는다. (여기서 L은 배열의 가장 왼쪽, R은 가장 오른쪽의 위치를 나타낸다) 
• left는 오른쪽으로, right는 왼쪽으로 이동
• left는 pivot보다 큰 수를 만나거나 pivot을 만나면 멈추고, 
• right는 pivot보다 작은 수를 만나거나 pivot을 만나면 멈춘다.
• 따라서 5가 3보다 크므로 left는 5에서 멈추고, 2가 3보다 작으므로 right는 2에서 멈춘다.

 

• left와 right가 멈췄을 때, left가 right보다 왼쪽에 있다면 left와 right 값을 교환해준다.
• 이후 left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동해준다.
• 위 과정을 left가 right 보다 오른쪽으로 올 때까지 반복한다.

 

• 6이 3보다 크므로 6에서 left가 멈춘다.
• right는 pivot을 만나서 멈춘다. 
• 이 때 left가 right보다 왼쪽에 있으므로 left와 right 값을 교환한다.
• left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동한다.
• left 가 right 보다 오른쪽에 있으므로 종료한다.

 

• right가 L보다 크다면 L부터 right까지 다시 위 과정을 재귀적으로 반복한다.
• left가 R보다 작다면 left부터 R까지 다시 위 과정을 재귀적으로 반복한다.

위와 같은 과정을 거치면 배열이 위와 같이 오름차순으로 정렬된다.

 

<구현>

void quicksort(int data[], int L, int R){
	int left=L, right=R;
    int pivot=data[(L+R)/2]; //피벗은 중간 인덱스 값
    int temp;
    do{
    	while(data[left]<pivot) //left보다 피벗이 크면 
        	left++; //오른쪽값으로 진행
        while(data[right]>pivot) //right가 피벗보다 크면
        	right--; //왼쪽값으로 진행
        if(left<=right){ //위의 반복문을 만족하지 않는 것들 정렬하기
        	temp=data[left];
            data[left]=data[right];
            data[right]=temp;
            left++; //정렬되도록 교환한 후 오른쪽값으로 진행
            right--; //왼쪽값으로 진행
        }
     }while(left<=right); //left가 right보다 오른쪽에 오면 반복문 탈출
     
     if(L<right) //왼쪽배열끝까지 아직 정렬 못했으므로 재귀적 호출 
     	quicksort(data, L, right); 
     if(left<R) //오른쪽 배열끝까지 아직 정렬 못했으므로 재귀적 호출
     	quicksort(data,left,R);
  }