퀵 정렬 (Quick Sort)

한유진·2021년 10월 24일
0

알고리즘

목록 보기
6/8

정의


  • 문제를 분할하고, 분할한 문제를 정복하여 합치는 알고리즘 (분할 정복)
  • 퀵정렬 : 선행작업을 한 다음 재귀적으로 작은 문제를 해결하면서 바로 끝낸다 : 하나의 리스트에 대해 비균등하게 나뉜다. [병합정렬 : 먼저 재귀적으로 작은문제를 해결한 다음 후처리 : 하나의 리스트를 절반으로 나눈다.]

과정


  1. 피벗을 하나 선택한다
  2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 작은값을 찾는다. 왼쪽은 피벗보다 큰 갑을 찾고 오른쪽에서부터는 피벗보다 작은 값을 찾는다
  3. 양 방향에서 찾은 두 원소를 교환한다
  4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을때까지 2번으로 돌아가 반복
  5. 엇갈린 기점을 기준으로 두개의 부분 리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐때까지 1번 과정 반복
  6. 인접한 부분리스트끼리 합친다

코드


왼쪽 피벗 선택 방식

private static void left_pivotSort(int[] a, int low, int high) {
	if( low >= high) 
    	return;
    int pivot = partition(a, low, high);
    left_pivotSort(a, low, pivot - 1);
    left_pivotSort(a, pivot + 1, high);
}
private static int partition(int[] a, int left, int right) {
	int low = left;
    int high = right;
    int pivot = a[left]; //부분리스트의 왼쪽 요소를 피벗으로 설정
    
    while(low < high) {
    
    	while(a[high] > pivot && low < high) {
        	high--; //high의 요소가 pivot보다 작거나 같은 원소를 찾을때까지 high 감소시킴
        }
        
        while(a[low] <= pivot && low < high) {
        	low++; //low의 요소가 pivot보다 큰 원소를 찾을때 까지 low를 증가시킴
        }
        
        swap(a, low, high);
    }
    swap(a, left, low);//pivot으로 설정했던 위치의 원소와 low가 가르키는 원소를 바꾼다.
    return low;

}
private static void swap(int[] a, int i, int j) {
	int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
    

오른쪽 피벗 선택 방식

private static void right_pivotSort(int[] a, int low, int high) {
	if( low >= high) 
    	return;
    int pivot = partition(a, low, high);
    right_pivotSort(a, low, pivot - 1);
    right_pivotSort(a, pivot + 1, high);
}
private static int partition(int[] a, int left, int right) {
	int low = left;
    int high = right;
    int pivot = a[right]; //부분리스트의 오른쪽 요소를 피벗으로 설정
    
    while(low < high) {
    
    	while(a[low] < pivot && low < high) {
        	low++; //high가 low보다크면서 low의 요소가 pivot보다 큰 원소를 찾을 때까지 low를 증가시킨다
        }
        
        while(a[high] >= pivot && low < high) {
        	high--; //high가 low보다 크면서, high의 요소가 pivot보다 작거나 같은 원소를 찾을 때까지 high를 감소시킨다
        }
        
        swap(a, low, high);
    }
    swap(a, right, high);//마지막으로 맨처음 pivot으로 설정했던 위치(a[right]) 의 원소와 high가 가리키는 원소를 바꾼다.
    
    return high;
}
private static void swap(int[] a, int i, int j) {
	int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
    

장점 & 단점


**장점**
  • 평균 시간 복잡도는 NlogN이며, 다른 NlogN알고리즘에 비해 속도가 매우 빠르다. merge sort에 비해 2~3배 정도빠르다
  • 추가적인 별도의 메모리를 필요로 하지 않으며 재귀 호출 스택 프레임에 의한 공간 복잡도는 logN으로 메모리를 적게 소비한다.

단점

  • 특정 조건하에 성능이 급격하게 떨어진다
  • 재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 경우 구현이 복잡해진다

시간복잡도


-평균비교연산 : O(2^i × N/2^i) = O ( N ) -평균시간복잡도 : 비교작업을 트리의 높이인 logN-1번 수행함 : O(N) X O(logN) = O(NlogN)

-가장 이상적으로 분할되었을때 수행시간 : 병합정렬과 같은 모양
T(N) = 2T(N/2) + O(N)
-평균적인 수행시간
T(N) = T(i - 1) + T(N - i) + O(N)

-최악의 시간복잡도: 정렬된 상태의 배열을 정렬할 때
: 분할이 한쪽으로 치중되는 경우
: 각 재귀 레벨에서 N개의 비교작업을 N번 재귀호출 함 = O(N^2)
T(N) = T(N-1) + O(N)

Q. Quicksort의 수행시간이 최악으로 나오는 경우가 어떤 경우인지 서술하고, 이러한 경우를 피할 수 있는 방법에 대해 설명하시오.

-항상 한쪽은 0개, 다른 쪽은 n-1개로 분할되는 경우

T(n) = T(0) + T(n-1) + O(n)
= T(n-1) + O(n)
= T(n-2) + T(n-1) + O(n-1) + O(n)
O(1) + O(2) + ... + O(n-1) + O(n)
=O(n^2)

-이미 정렬된 입력데이터 ( 마지막 원소를 피봇으로 선택하는 경우)

피할 수 있는 방법 : dual-pivot사용하기
임계값을 설정하여 일정 크기 이하로 떨어질 경우 정렬된 배열에서 좋은 성능을 발휘하는 insertion sort(삽입정렬)을 하도록 바꾸면 거의 정렬된 상태에서도 성능 하락을 방지할 수 있다.

profile
열정열정

0개의 댓글