[알고리즘] 퀵 정렬

목차

1. 퀵정렬의 개념
2. 퀵정렬의 장단점
3. 퀵정렬의 코드구현(JAVA)

퀵정렬의 개념

• 퀵정렬은 병합 정렬과 마찬가지로 분할 정복 알고리즘을 이용한 정렬 알고리즘이며 가장 빠른 정렬 알고리즘.

퀵정렬의 방식

퀵정렬의 장단점

장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

단점

• 불안정 정렬(Unstable Sort) 이다.
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

퀵정렬의 구현(JAVA)

public class QuickSort {
	private static  void quickSort(int[]arr,int start,int end) {
		int part = partition(arr,start,end);
		if(start < part -1) {
			quickSort(arr,start,part-1);
		}
		
		if(end > part) {
			quickSort(arr, part, end);
		}
	}
	
	private static int partition(int[]arr,int start, int end) {
		int pivot = arr[(start+end)/2];
		while(start <= end) {
			 while(arr[start]<pivot) start++;
	            while(arr[end]>pivot) end--;
	            if(start<=end) {
	                swap(arr,start,end);
	                start++;
	                end--;
	            }
		}
		return start;
	}
	
	private static void swap(int[]arr,int start, int end) {
		int tmp=arr[start];
        arr[start]=arr[end];
        arr[end]=tmp;
        return;
	}
	
	public static void main(String[] args) {
		int[] arr= {7,4,2,8,3,5,1,6,10,9};
        quickSort(arr,0,arr.length-1);
        for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+",");
        }
	}
}