퀵정렬(Quick Sort)

퀵 정렬

• 데이터의 갯수가 적을 때는 괜찮지만 데이터의 갯수가 10만 개만 넘어가도 보통의 상황에서
  선택,버블,삽입 정렬 알고리즘을 사용하기가 힘들다. 이런 경우 퀵 정렬을 사용한다면
  아무리 많은 양의 데이터라도 빠르게 정렬을 할 수 있다.
• 대표적인 분할 정복 알고리즘
• c 라이브러리로 제공하는 sort() 함수가 퀵 정렬을 기반으로 구현되어 있다.
• 이미 정렬이 되어있거나 거의 정렬되어 있는 데이터에 사용할 때는 성능이 매우 떨어짐

 

퀵 정렬의 시간 복잡도

평균  :  O(N * logN)    -> 반씩 쪼개서 정렬하기 떄문에 logN인 것이다.

최악  :  O(N^2)

 

퀵 정렬이 최악인 경우에도 O(N * logN)을 보장하는 방법

- STL 라이브러리에서 제공하는 sort() 함수는 퀵 정렬을 기반으로 하되 별도의 처리를 거쳐
  최악의 경우에도 O(N * logN)을 보장한다.

 

 

퀵 정렬 동작 방식

1. 데이터들 중 특정한 값을 피벗(Pivot)으로 정한다.  =>     기준값 설정

2. 피벗을 기준으로 왼쪽에는 피벗보다 작은 값들 오른쪽에는 피벗보다 큰 값들이 모이도록 한다.

3. 왼쪽과 오른쪽을 각각 퀵 정렬을 수행한다.           =>      재귀 호출

4. 최종적으로 전체 값들이 정렬된다.  

 

 

배열의 중앙을 피벗(Pivot)으로 잡고 하는 법

 

 

  (1)  left, right, pivot 설정

 

 

(2) left : pivot보다 큰 값을 찾을 때까지 이동(left++) / right : pivot보다 작은 값을 찾을 때까지 이동(right--)

   - pivot보다 큰 값(left)과 작은 값(right)을 찾고, 서로의 값을 교환

   - 교환한 후 left++ , right--

 

 

(3) 위와 같은 과정을 반복해서 피봇보다 큰 값(left)과 작은 값(right) 찾아서 교환

    - 교환한 후 left++, right--;

 

 

(4) 값을 교환한 후 left와 right가 엇갈림 ( ☆☆☆☆☆ )

- left와 right가 엇갈려 left가 더 커지게 된 경우 

   => right와 left 두 부분으로 분할해서 따로 퀵 정렬 수행!!

 

 

(5) 분할된 두 부분을 각각 퀵 정렬 수행 ( 재귀 호출 )

 

 

퀵 정렬 구현 코드

#include<iostream>
using namespace std;

int data[] = {5,1,6,3,4,2,7};

void quickSort(int start, int end){
	if(start >= end) return;
    
    int left = start;
    int right = end;
    int pivot = (start + end) / 2;
    
    while(left < right){
    	while(data[left] < data[pivot]) left++;
        while(data[right] > data[pivot]) right--;
        
        if(left <= right){
        	swap(data[left], data[right]);
            left++;
            right--;
        }
    }
	
    quickSort(start,right);
    quickSort(left,end);
}

int main(){
	int i;
    quickSort(0,6);
    for(i = 0; i < 7; i++){
    	printf("%d ",data[i]);	
    }    
}