퀵 정렬(Quick Sort)

📌 퀵 정렬(Quick Sort)

⭐ 개념

• 시간복잡도 O(nlogn)
• pivot을 선정하여 pivot을 기준으로 작은 값은 왼쪽 큰 값은 오른쪽에 배치하고 계속 분할하여 정렬하는 알고리즘

⭐ 작동순서

💡 왼쪽 pivot방식

• partition에서 제일 왼쪽값을 pivot으로 설정
• pivot보다 작은값을 만날때까지 hi--
• pivot보다 큰값을 만날때까지 lo++
• hi랑 lo swap

⭐ 코드

💡 <왼쪽 pivot 방식>

public static void main(String[] args) {
	int[] arr = {67, 29, 34, 20, 11, 70, 53};
	l_pivot_sort(arr, 0, arr.length-1);
}

public static void l_pivot_sort(int[] a, int lo, int hi) {
		
	// 정렬할 원소가 1개 이하이므로 종료
	if(lo >= hi) {
		return;
	}		
    
	int pivot = partition(a, lo, hi);	
		
	l_pivot_sort(a, lo, pivot - 1);
	l_pivot_sort(a, pivot + 1, hi);
}

public static int partition(int[] a, int left, int right) {
	int lo = left;
	int hi = right;
    
    // 왼쪽 요소를 pivot으로 설정
	int pivot = a[left];
    
	while(lo < hi) {
    	// 오른쪽에 pivot보다 작은값을 만날때까지 hi--
		while(a[hi] > pivot && lo < hi) {
			hi--;
		}
        // 왼쪽에 pivot보다 큰 값을 만날때까지 lo++
		while(a[lo] <= pivot && lo < hi) {
			lo++;
		}
		swap(a, lo, hi);
	}
	swap(a, left, lo);
	return lo;
}

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

💡 <오른쪽 pivot 방식>

public static void main(String[] args) {
	int[] arr = {67, 29, 34, 20, 11, 70, 53};
	r_pivot_sort(arr, 0, arr.length-1);
}

public static void r_pivot_sort(int[] a, int lo, int hi) {
		
	// 정렬할 원소가 1개 이하이므로 종료
	if(lo >= hi) {
		return;
	}		
    
	int pivot = partition(a, lo, hi);	
		
	r_pivot_sort(a, lo, pivot - 1);
	r_pivot_sort(a, pivot + 1, hi);
}

public static int partition(int[] a, int left, int right) {
	int lo = left;
	int hi = right;
    
    // 오른쪽 요소를 pivot으로 설정
	int pivot = a[right];
    
	while(lo < hi) {
    	// 왼쪽에 pivot보다 큰 값을 만날때까지 lo++
    	while(a[lo] < pivot && lo < hi) {
			lo++;
		}
        // 오른쪽에 pivot보다 작은값을 만날때까지 hi--
		while(a[hi] >= pivot && lo < hi) {
			hi--;
		}
		
		swap(a, lo, hi);
	}
	swap(a, right, hi);
	return hi;
}

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

💡 <중간 pivot 방식>

public static void main(String[] args) {
	int[] arr = {67, 29, 34, 20, 11, 70, 53};
	m_pivot_sort(arr, 0, arr.length-1);
}

public static void m_pivot_sort(int[] a, int lo, int hi) {
		
	// 정렬할 원소가 1개 이하이므로 종료
	if(lo >= hi) {
		return;
	}		
    
	int pivot = partition(a, lo, hi);	
		
	m_pivot_sort(a, lo, pivot);
	m_pivot_sort(a, pivot + 1, hi);
}

public static int partition(int[] a, int left, int right) {
	int lo = left-1;
	int hi = right+1;
    
    // 가운데 요소를 pivot으로 설정
	int pivot = a[(left+right) / 2];
    
	while(true){
    	do{
        	lo++;
        }while(a[lo] < pivot);
        
        do{
        	hi--;
        }while(a[hi] > pivot && lo <= hi);
        
        if(lo >= hi){
        	return hi;
        }
        swap(a, lo, hi);
    }
}

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