[자바] 정렬 알고리즘 -퀵 정렬

퀵 정렬(Quick Sort)

- 선택, 버블, 삽입정렬 알고리즘은 Worst case인 경우에 모두 시간 복잡도를 O(N^2)을 가지게 되는데 보통 데이터 갯수가 무수히 많다고 가정하는 상황에서는 사용하기 어려운 정렬들이다.

 

- 퀵 정렬은 분할 정복 알고리즘으로 특정한 배열이 있을때 그 배열을 반복적으로 분할 배열의 원소들을 나누어서 계산한다. 빠른 알고리즘이다.

 

- 사용 방법

 특정한 값을 기준으로 큰 숫자 집합과 작은 숫자 집합으로 나눈다. Pivot이라는 명칭으로 원소를 정하게 되는데 이 Pivot을 기준으로 비교해서 Pivot이 가운데에 오게 왼쪽 오른쪽으로 나누게 되는 것이다.

 

더 좋은 방법은 배열을 정렬할때 Pivot을 처음 중간 끝을 기준으로 3개를 골라서 이 3개를 비교해서 중간값을 이용해서 Pivot값을 결정하고 하면 더 효율적인 알고리즘이 된다.

 

 일단 왼쪽값을 Pivot으로 잡았을때

public class LeftQuickSort {
	
	public static void sort(int []a) {
		mergesort(a,0,a.length-1);
	}
	
	public static void mergesort(int []a, int left, int right) {
		
		if(left>=right)
			return;
		
		int pivot_index=subsort(a,left,right);
		mergesort(a,left,pivot_index-1);
		mergesort(a,pivot_index+1,right);
		
		
	}
	
	public static int subsort(int []a,int left, int right) {
		int pivot=a[left];
		int i=left;
		int j=right;
		
		while(i<j) {
			while(i<j&&a[j]>pivot) {
				j--;}
			while(i<j&&a[i]<=pivot) {
				i++;}
			//if(i<j) - 필요가 없다.
			swap(a,i,j);
			
		}
		swap(a,left,i);
		
		return i;
	}

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

 while문으로 i<j&&a[j]>pivot에 해당하는 조건들이 있는데 while문 안의 2개의 while문들의 순서가 중요한 것같다.

만약 i++;에 해당하는 것을 먼저하게 되면 i가 먼저 증가하게 되어 swap(a,left,i);할때 이상해진다. 왜냐하면 i가 너무 많이 증가된 상태로 바꾸는 경우가 생기기 때문이다. 그리고 <=pivot 에 대한 부호가 쓰였는데 이것은 왼쪽의 값을 pivot으로 선택했을때에만 해당된다. 안하게 된다면 pivot에 대한것을 검사할때 pivot도 swap을 해버리기 때문이다.

만약 햇갈린다면 6개나 7개의 배열을 직접 손으로 만들어 놓고 연습장에 풀어보면 될 것이다.

 

가운대값을 Pivot으로 잡았을때

public class MediumQuickSort {
	
	public static void sort(int []a) {
		mergesort(a,0,a.length-1);
	}
	
	public static void mergesort(int []a, int left, int right) {
		
		if(left>=right)
			return;
		
		int pivot_index=subsort(a,left,right);
		mergesort(a,left,pivot_index-1);
		mergesort(a,pivot_index+1,right);
		
		
	}
	
	
	public static int subsort(int []a,int left, int right) {
		int pivot_index=(left+right)/2;
		int pivot=a[pivot_index];
		int i=left;
		int j=right;
		
		while(i<j) {
			while(a[i]<pivot)
				i++;
			while(a[j]>pivot&&i<j)
				j--;
			

			
			swap(a,i,j);
		}
		return i;
	}

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

이에 해당하게 되는데 특징은 i가 우리가 지정한 피벗값을 지나 swap이 될 수 있다는 것이다.

퀵정렬 사진

이그림과 같이 하지만 내 위에서의 코드는 이 그림과는 다른데 특이한 점은 

mergesort(a,left,pivot_index-1);
mergesort(a,pivot_index+1,right);

//오류X
mergesort(a,left,pivot_index);
mergesort(a,pivot_index+1,right);
        
//오류 발생
mergesort(a,left,pivot_index-1);
mergesort(a,pivot_index,right);
 //StackOverflowError가 발생하게 된다.

왜 오류가 발생하는지는 에러메시지를 봤음에도 정확히는 잘 모르겠다 나중에 천천히 다시 해봐야겠다.

 

장점

특정 상태가 아닌 이상 시간 복잡도는 NlogN이며, 다른 NlogN 알고리즘에 비해 대체적으로 속도가 매우 빠르다. 

추가적인 별도의 메모리를 필요로하지 않으며 재귀 호출 스택프레임에 의한 시간복잡도는 logN으로 메모리를 적게 소비한다.

 

 

 

단점

특정 조건하(피벗 값에 따라서 편향되게 분할 될 수 있다.)에 성능이 급격하게 떨어진다.

재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 경우 그 구현이 매우 복잡해진다.