[알고리즘] 퀵 정렬

파티셔닝을 이용한 정렬방법

1. 기준값을 정한다.
2. 첫번째부터 차례로 비교해나가면서
    기준값보다 작으면 왼쪽 그룹의 끝자리+1과 위치를 바꾼다.

퀵 정렬 이미지

퀵 정렬의 수도코드

 

 

수행시간

Balanced Partitioning : 파티셔닝의 크기가 n/2로 줄어드는 경우
          =>  높이 logN * 각 층별 N번의 연산을 수행
          =>  O(NlogN)
UnBalanced Partitioning : 파티셔닝의 크기가 1과 n-1개로 줄어드는 경우
          => 높이 N-1 * 각 층별 N-1번의 연산을 수행 
          => O(N²)

 

* Unbalanced Partitioning(최악의 경우)를 피하기 위해 파티셔닝의 크기를 랜덤하게 가져가는  Randomized QuickSort가 등장함.

 

JAVA

package algorithm;

import java.util.Arrays;

public class QuickSort {
	
	static int[] arr;
	static int[] tmp;
	
	public void quickSort(int start, int end) {
		
		if(start<end) {
			int mid = partition(start, end);
			quickSort(start, mid-1);
			quickSort(mid+1, end);
		}
		
	}

	private int partition(int start, int end) {
		
		int mid = (start+end)/2; //파티션 기준 위치(가운데)
		
		int pivot = arr[end];	//파티션 비교 기준 -> 가장 끝 값
		
		/*하나씩 돌면서 pivot과 비교 > pivot보다 작으면 위치 바꾸기 */
		for(int i = start; i<end; i++) {
			if(arr[i]<pivot) {
				swap(i, start);
				start++;
			}
		}
		/*마지막 위치를 파티션 기준 위치(가운데)로 이동함.*/
		swap(mid,end);
		
		return mid;
	}

	public void swap(int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}


	public static void main(String[] args) {
		arr = new int[] {3, 5, 1, 6, 9, 2, 4};
		tmp = new int[arr.length];
		QuickSort f= new QuickSort();
		f.quickSort(0, arr.length-1);
		System.out.println(Arrays.toString(arr));
		
	}

}