[알고리즘] 퀵 정렬 (Quick Sort)

퀵 정렬

 

Merge Sort와 비슷하게 Divide and Conquer기법을 사용하고 Recursive Function을 이용한다.

 

매 재귀마다, Quick Sort는 Pivot이라는 정렬의 기준이 될 기준을 선정한다.

 

효율적인 Pivot을 선정하는 방법은 다음에 설명하기로 하고, 우선 Pivot을 현재 배열의 마지막 데이터로 하기로 하자.

 

그 Pivot을 기준으로 Pivot보다 작은 데이터들은 Pivot의 왼쪽으로, 큰 데이터들은 Pivot의 오른쪽으로 옮긴다.

 

그러면, Pivot은 제 위치를 찾게 되고(정렬이 끝난 뒤의 위치에 존재한다)

정렬되지 않은 배열은 Pivot의 왼쪽과 오른쪽이다. (2개의 정렬되지 않은 부분배열로 나누어진다.)

 

이제 정렬되지 않은 부분배열에 대해서 Quick Sort를 반복한다.

 

이 과정을 부분 배열의 갯수가 1개 이하가 될 때까지 반복하면 정렬이 완료된다.

 

Java Code

	public static void quickSort(int[] array, int start, int end){

		if(end- start<= 0 || end>=array.length || start<0){

			return;

		}

		

		int pivot= end;

		int index= start;

		for(int j= start; j<=end; j++){

			if(j== pivot){

				continue;

			}

			if(array[j] <= array[pivot]){

				int temp= array[j];

				array[j]= array[index];

				array[index]= temp;	

				index++;

			}

		}

		int temp= array[pivot];

		array[pivot]= array[index];

		array[index]= temp;

		

		quickSort(array, start, index-1);

		quickSort(array, index+1, end);

	}

 

시간복잡도

 

Quick Sort는 평균적으로 Time Complexity가 O(n*log n) 이다.

 

그러나 Worst Case(Pivot을 잘못 선정했을 때)일 때 O(n^2)이 된다.

 

따라서 Pivot을 잘 선정하는 것이 Quick Sort의 성능을 좌우한다고 할 수 있다.