기본 알고리즘 - Quick Sort

1. 개요

  - Quick Sort 알고리즘은 worst case 에 n^2 의 복잡도를 가지나 평균적으로 nlog n 의 복잡도를 갖는다.

  - Concept

     1. 주어진 배열에서 기준값을 하나 잡는다.

     2. 기준값을 기준으로 작은 값은 기준 값 앞으로 큰 값은 기준값뒤로 배치한다.

         이 때, 왼쪽, 오른쪽의 내용은 정렬은 되지 않고 기준 값 대비 크고 작음에 따라서만 배치되는 점을 유의한다.

     3. 기준 값을 제외하고 앞 쪽 배열과 뒤쪽 배열에 대해 다시 QuickSort를 수행한다.

     4. 이러한 과정을 배열의 크기가 2가 될 때까지 수행한다.

   

2. 알고리즘

 

// p : 시작 Index

// q : 종료 Index

// r : 기준값을 저장하는 Index (편의상 가장 끝값을 사용했다.)

QuickSort (A, p, q)

{

int l_idx = q-1; // 새로운 큰 값이 저장될 위치

 

// Out Condition

if (p >= q)

return;

 

for (i = p ; i < q && i <= l_idx; i++)

{

if ( A[i] > A[q])

{

swap(A, i--,l_idx--);

}

}

 

// 기준값보다 큰 값이 저장되어 있는 array의 값과 기준값을  SWAP 한다.

swap(A,  l_idx+1,q);

 

QuickSort(A,p,l_idx);    // 기준값보다 작은 값이 모여있는 배열을 재귀 sort한다.

QuickSort(A,idx+2,q);    // 기준값보다 큰 값이 모여있는 배열을 재귀 sort 한다.

}

 

3. 실제 구현 (Java)

 

 

	// p : 시작 Index
	// q : 종료 Index 
	// r : 기준값을 저장하는 Index (편의상 가장 끝값을 사용했다.)
	void QuickSortImpl (int[] A, int p, int q)
	{

		int l_idx = q-1; // 새로운 큰 값이 저장될 위치 

		// Out Condition 
		if (p >= q)
			return; 

		for (int i = p ; i < q && i <= l_idx; i++)
		{
			if ( A[i] > A[q])
			{
				swap(A, i--,l_idx--);
			} 
		}

		// 기준값보다 큰 값이 저장되어 있는 array의 값과 기준값을  SWAP 한다. 
		swap(A,  l_idx+1,q);

		QuickSortImpl(A,p,l_idx);    // 기준값보다 작은 값이 모여있는 배열을 재귀 sort한다.
		QuickSortImpl(A,l_idx+2,q);    // 기준값보다 큰 값이 모여있는 배열을 재귀 sort 한다. 

	}

4. 주의사항
  - Array가 정렬되어 있을 경우, Worst Case n^2 알고리즘이 수행된다. (왜냐면, 기준 값에 대해 할일이 없으므로 sorting array 크기가 항상 1씩만 줄어들기 때문이다.)
  - 이렇게 되면, 단순히 배열의 크기가 4000 만 되어도 stack overflow가 발생한다. 
  - 이를 해결하기 위해서는 JAVA Run Configuration 에서 stack size를 1m로 확장해주면 된다.