퀵정렬(Quick Sort)

퀵정렬: 하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 빠르게 정렬하는 방법

-> 특정한 값 피벗(Pivot)을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다

 

 

EX)

 

(3) 7 8 1 5 9 6 10 2 4

 

3을 피벗으로 지정

3보다 큰 숫자를 왼쪽에서 찾고 3보다 작은 숫자를 오른쪽부터 찾는다. 

3보다 큰 수: 7

3보다 작은 수: 2 

이때 큰값과 작은 값의 위치를 바꿔준다

 

(3) 2 8 1 5 9 6 10 7 4

3보다 큰 수: 8

3보다 작은 수: 1

 

(3) 2 1 8 5 9 6 10 7 4

3보다 큰 수: 8

3보다 작은 수: 1

이때 큰값의 인덱스와 작은값의 인덱스가 엇갈린다

이럴때는 피벗값(3)과 작은값(1)을 바꿔준다

 

1 2 (3) 8 5 9 6 10 7 4

따라서 피벗 값이었던 3의 왼쪽에는 3보다 작은 값이 존재하고 오른쪽에는 3보다 큰 값이 존재하게 된다

 

3을 기준으로 좌우로 분할한다

 

(1) 2 3 (8) 5 9 6 10 7 4

3의 왼쪽에서는 가장 앞에 있는 1이 피벗이 되고  오른쪽에서는 가장 앞에 있는 8이 피벗이 된다

 

1보다 큰수: 2

1보다 작은수: 작은게 없어서 자기 자신을 선택한다

이때 큰값의 인덱스와 작은값의 인덱스가 엇갈린다

이럴때는 피벗값(1)과 작은값(1)을 바꿔준다

 

1 2 3 (8) 5 9 6 10 7 4

 

8보다 큰수: 9

8보다 작은수: 4 

 

1 2 3 (8) 5 4 6 10 7 9

 

8보다 큰수: 10

8보다 작은수: 7 

 

1 2 3 (8) 5 4 6 7 10 9

 

8보다 큰수: 10

8보다 작은수: 7 

이때 큰값의 인덱스와 작은값의 인덱스가 엇갈린다

이럴때는 피벗값(8)과 작은값(7)을 바꿔준다

 

1 2 3 7 5 4 6 8 10 9

->

1 2 3 7 5 4 6 8 10 9

->

1 2 3 6 5 4 7 8 10 9

->

.....

-> 

1 2 3 7 5 4 6 8 10 9

 

Java code

public class QuickSort {
	public static void main(String[] args) {
		int []data= {1,10,5,8,7,6,4,3,2,9};
		quickSort(data,0,data.length-1);
		show(data);
	}


	public static void show(int[] data) {
		int i;
		for(i=0;i<data.length;i++) {
			System.out.print(data[i]+" ");
		}
	}

	public static void quickSort(int[] data,int start,int end) {
		if(start >= end){ //원소가 1개인 경우 그대로 두기
			return;
		}

		int pivot=start; //피벗은 첫번쨰 요소 
		int i=start+1; //i=1
		int j=end; //j=9
		int temp;

		while(i<=j) { //엇갈릴 때까지 반복
			while(i<=end && data[i]<=data[pivot] ) {
				i++; //피벗값보다 큰 값을 만날때까지 인덱스 증가
			}

			while(j>start && data[j]>=data[pivot]) {
				j--; //피벗값보다 작은 값을 만날때까지 인덱스 감소 
			}

			if(i>j) { //엇갈리면 피벗과 작은값을 교체
				temp=data[j];
				data[j]=data[pivot];
				data[pivot]=temp;
			}
			else{ //아직 엇갈리지 않으면 피벗보다 큰값과 피벗보다 작은값 교체
				temp=data[i];
				data[i]=data[j];
				data[j]=temp;
			}

		}
		quickSort(data,start,j-1);
		quickSort(data,j+1,end);
	}
}

 

퀵 정렬의 평균 시간 복잡도는 O(N * logN)이다

 

그러나 최악 시간 복잡도는 O(N^2)이다

EX)

1 2 3 4 5 6 7 8 9 10

 

위와 같이 이미 정렬이 되어 있는 경우 퀵 정렬의 시간복잡도는 O(N^2)에 가깝다

 

따라서 문제에서 복잡도 O(N * logN)을 요구하는 경우 퀵정렬을 사용하면 틀리기도 한다