퀵 정렬(Quick Sort)

"퀵 정렬"

     : 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나누는 정렬 방법

 

• 시간 복잡도 : O(N * logN)
• 최악의 시간 복잡도 : O(N^2)

 

• 대표적인 '분할 정복' 방법을 채택한 알고리즘
• 재귀함수로 구현

 

• "피벗(Pivot)" : 기준 값
• 보통 맨 앞 요소를 피벗으로 설정

 

class Sort {
	
	public void Quick_Sort(int[] arr, int start, int end) {
    
		if(start >= end) // 원소가 한 개인 경우, 그대로 두기
			return;
		
        
		int pivot = start; // 피벗은 첫 번째 원소
		int i = start + 1;
		int j = end;
		
        
		while(i <= j) { // 엇갈릴 때까지 반복
			
			while(i <= end && arr[i] <= arr[pivot]) // 피벗보다 큰 값을 만날 때
				i++;
			
            
			while(j > start && arr[j] >= arr[pivot]) // 피벗보다 작은 값을 만날 때
				j--;
			
            
			if(i > j) { // 현재 엇갈린 상태이면, 피벗과 교체
				int temp = arr[j];
				arr[j] = arr[pivot];
				arr[pivot] = temp;
			}
			else { // 엇갈리지 않은 상태이면, i와 j를 교체
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		
        
		Quick_Sort(arr, start, j - 1);
		Quick_Sort(arr, j + 1, end);
	}
}

 

   ※ 내림차순 버전

class Sort {
	
	public void Quick_Sort(int[] arr, int start, int end) {
    
		if(start >= end)
			return;
		
        
		int pivot = start;
		int i = start + 1;
		int j = end;
		
        
		while(i <= j) {
			
			while(i <= end && arr[i] >= arr[pivot]) // arr[i] >= arr[pivot]으로 수정
				i++;
			
            
			while(j > start && arr[j] <= arr[pivot]) // arr[j] <= arr[pivot]으로 수정
				j--;
			
            
			if(i > j) {
				int temp = arr[j];
				arr[j] = arr[pivot];
				arr[pivot] = temp;
			}
			else {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		
        
		Quick_Sort(arr, start, j - 1);
		Quick_Sort(arr, j + 1, end);
	}
}