퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

알고리즘이 매우 빠르다라고 해서 붙여진 이름이다.

기준이 되는 피벗(pivot)을 설정하고, 그룹을 반복적으로 나누어서 정렬을 하는 알고리즘이다.

 

퀵 정렬은 피벗을 배열의 왼쪽 끝으로 설정하냐, 오른쪽 끝으로 설정하냐, 가운데로 설정하냐에 따라서 속도가 달라진다.

 

 

퀵 정렬의 알고리즘을 간단히 설명하면 이렇다.

배열의 왼쪽 끝 요소를 가리키는 커서를 pl, 오른쪽 끝 요소를 가리키는 커서를 pr 로 한다.

그리고 피벗을 가운데 값인 8로 한다고 하자. 

피벗을 기준으로 왼쪽에 있는 구역을 A 구역, 오른쪽에 있는 구역을 B 구역이라고 할 때,

A 구역에서는 pl을 오른쪽으로 이동시키면서 8보다 큰 값들을 찾아서 B 구역으로 넘기고,

B 구역에서는 pr을 왼쪽으로 이동시키면서 8보다 작은 값들을 찾아서 A 구역으로 넘기는 것이다.

그렇게 되면 결과적으로 A 구역에는 8보다 작은 값들이, B 구역에는 8보다 큰 값들이 위치하게 된다.

그리고 나서 아래의 배열을 두 그룹으로 나눈 후, 위 과정을 똑같이 반복하면 된다.

 

 

시간 복잡도 : O(NlogN) 

최악의 시간 복잡도 : O(N²)

퀵 정렬은 배열의 초기상태나 피벗의 위치에 따라서 최악의 경우 시간 복잡도가 O(N²) 가 될 수 있다.

 

 

알고리즘 : 

1. 피벗을 설정한다.

 

2. 배열의 시작 인덱스를 left, 마지막 인덱스를 right라고 할 때,

    - pl은 left부터 시작하여 피벗보다 크거나 같은 값이 있을 때까지 오른쪽으로 이동한다.

      (단, pl이 right보다 작거나 같을때까지만 이동)

    - pr은 마지막부터 시작하여 피벗보다 작거나 같은 값이 있을 때까지 왼쪽으로 이동한다.

      (단, pr이 left보다 크거나 같을때까지만 이동)

 

3. pl과 pr 이 이동을 멈추면, pl<=pr 이면 arr[pl] 과 arr[pr] 을 서로 교환(swap)한다.

   교환이 끝나면 pl은 오른쪽으로 하나 이동, pr은 왼쪽으로 하나 이동한다.

 

4. pl과 pr이 교차할 때까지, 즉, pl > pr 일 때까지 2,3번을 반복한다.

 

5. pl 과 pr이 교차하면,

   시작 인덱스를 left, 끝 인덱스를 pr로 하는 그룹으로 쪼개어서 1,2,3번 과정을 반복한다.

   (단, left < pr 조건을 만족해야 함)

   마찬가지로, 시작 인덱스를 pl, 끝 인덱스를 right로 하는 그룹으로 쪼깨어서 1,2,3번 과정을 반복한다.

   (단, pl < right 조건을 만족해야 함)

 

6. 더 이상 작은 그룹으로 쪼갤 수 없으면 종료한다.

   

  

 

[예제]

배열 arr의 요소가 차례대로 5 9 3 1 8 4 6 2 7 일 때, 이 배열을 오름차순으로 정렬하기

 

이번 예제에서는 피벗을 가운데값으로 설정할 것이다.

배열의 왼쪽 끝 인덱스를 left = 0, 오른쪽 끝 인덱스를 right = 8 이라고 하면,

처음 초기값은 pl = left, pr = right, pivot = 8 이다.

 

 

 

pl에 위치한 값이 8보다 클 때까지 pl이 오른쪽으로 이동하면, pl은 9가 있는 1번 인덱스에서 멈춘다.

pr에 위치한 값이 8보다 작을 때까지 pr이 왼쪽으로 이동하면, pr은 7이 있는 8번 인덱스에서 멈춘다.

arr[1] 과 arr[8] 을 서로 교환한다.

 

 

교환이 끝나면 pl은 하나 증가하여 3을 가리키고, pr은 하나 감소하여 2를 가리킨다.

pl이 8보다 크거나 같을 때까지 이동하면 pl = 4 에서 이동을 멈춘다.

pr의 경우, arr[7] = 2 이므로 8보다 작으므로 이동을 하지 않는다. pr = 7

pl과 pr의 이동이 끝나면 arr[4] 와 arr[7]를 교환한다.

 

 

교환이 일어난 후, pl은 오른쪽으로 한칸 이동하여 pl = 5가 되고, pr은 왼쪽으로 한칸 이동하여 pr = 6가 된다.

pl 이 8보다 크거나 같은 값이 나올 때까지 이동하면 pl = 7 에서 이동을 멈춘다.

pr은 arr[6] = 6이 8보다 작으므로 pr = 6 에서 이동을 하지 않는다.

pr < pl 이 되었으므로 pl과 pr이 교차가 일어나 반복문이 종료된다.

left = 0을 시작으로하고 pr = 6을 끝으로 하는 그룹과, pl = 7을 시작으로 하고 right = 8을 끝으로 하는 그룹으로 나뉘어진다.

 

 

먼저 왼쪽 그룹부터 보자.

초기 상태는 pl = 0, pr = 6, pivot = 1 이다.

arr[0] = 5로 1보다 크므로 pl은 pl = 0 에서 더 이상 움직이지 않는다.

pr은 1보다 작거나 같은 수를 찾을 때까지 왼쪽으로 이동한다. pr = 3 일 때 이동을 멈춘다.

arr[0] 과 arr[3]를 교환한다.

 

 

교환이 일어난 후, pl은 오른쪽으로 하나 증가하여 pl = 1, pr은 왼쪽으로 하나 감소하여 pr = 2가 된다.

pl은 arr[1] = 7 이므로 피벗보다 크기 때문에 이동을 하지 않고 멈춘다.

pr은 피벗보다 작거나 같을 때까지 왼쪽으로 이동하면 pr = 0 일 때 이동을 멈추게 된다.

pr < pl 이 되었으므로 pl과 pr이 교차가 일어나 반복문이 종료된다.

left < pr이 성립하지 않으므로 왼쪽 그룹은 만들어지지 않는다.

pl = 1을 시작으로 하고 right = 6을 끝으로 하는 그룹이 생긴다.

 

 

이제 다시 돌아가서 오른쪽 그룹(8, 9)을 보자.

pl은 arr[7] = 8 이므로 피벗과 크거나 같다는 조건을 만족하므로 pl = 7에서 이동을 하지 않는다.

pr은 8보다 작거나 같을 때까지 이동하면, pr = 7에서 이동을 멈춘다.

arr[7] 와 arr[7]을 교환한다. (같은 위치의 값끼리 교환하므로 결과는 동일)

교환 후에 pr은 오른쪽으로 하나 이동하지만, pl은 left<=pl 조건을 만족해야 하므로 이동하지 않는다.

pr < pl 이 되었으므로 pl과 pr이 교차가 일어나 반복문이 종료된다.

 

 

이제 7 3 5 2 4 6 을 퀵정렬해보자.

초기 상태는 pl = 1, pr = 6, pivot = 5 이다.

pl = 1 일 때 5보다 크거나 같은 조건을 만족하므로 더 이상 이동을 하지 않는다.

pr은 피벗인 5보다 작거나 같을 때까지 이동하면 pr = 5 에서 이동을 멈춘다.

arr[1] 과 arr[5] 를 교환한다.

 

 

교환이 일어나고, pl = 2로 오른쪽으로 한칸 이동하며 pr = 4로 왼쪽으로 한칸 이동한다.

pl이 5보다 크거나 같을 때까지 이동하면 pl = 3 에서 이동을 멈춘다.

pr은 arr[4] = 2 가 피벗인 5보다 작으므로 더 이상 이동하지 않는다.

arr[3] 과  arr[4] 를 교환한다.

교환이 일어나고, 또다시 pl은 오른쪽으로 pr은 왼쪽으로 이동하게 되면 pr< pl이 되어 반복문이 종료된다.

그리고 left = 1을 시작으로 하고 pr = 3을 끝으로 하는 그룹과, pl = 4을 시작으로 하고 right = 6을 끝으로 하는 그룹으로 나뉘어진다.

 

 

왼쪽 그룹부터 먼저 진행해보자.

pl이 가리키는 4은 피벗보다 크고, pr이 가리키는 2는 피벗보다 작으므로 

arr[1] 와 arr[3] 을 교환한다.

교환하고 pl은 오른쪽으로 한칸, pr은 왼쪽으로 한칸 이동하면 또 pl과 pr이 이동을 멈춘다.

(pl은 arr[pl]>=pivot 조건을 만족하고, pr은 arr[pr]<=pivot 조건을 만족하므로)

arr[2] 와 arr[2] 를 교환한다.

또 다시 pl은 오른쪽으로 한칸, pr은 왼쪽으로 한칸 이동하면 pr < pl 이 되어 반복문이 종료된다.

 

나머지 그룹도 똑같이 진행한다.

여태까지 방법과 동일하므로 자세한 설명은 생략한다.

마지막 그룹까지 마치고 나면 최종적으로 배열 arr이 오름차순으로 정렬된 것을 확인할 수 있다.

 

소스코드 : 

	public static void quickSort(int[] arr, int left, int right) {

		int pl = left;
		int pr = right;
		int pivot = arr[(pl + pr) / 2];

		do {

			while (pl <= right && arr[pl] < pivot)
				pl++;
			while (left <= pr && arr[pr] > pivot)
				pr--;

			if (pl <= pr)
				swap(arr, pl++, pr--);

		} while (pl <= pr);

		if (left < pr)
			quickSort(arr, left, pr);
		if (pl < right)
			quickSort(arr, pl, right);

	}