[알고리즘] 퀵정렬 향상시키기 ( 스택 )

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

 

 

이전 포스팅에서 재귀(recursive)함수를 

활용한 퀵 정렬(Quick Sort)를 알아보았다.

 

일반적으로 퀵정렬은 재귀함수로 구현되지만

재귀함수는 한 가지 문제가 있다.

 

재귀는 메소드를 반복적으로 호출한다.

 

 

JVM 메모리 구조

 

메소드는 본인의 영역이 있어야 하므로 호출할 때마다, Stack 영역의 메모리를 차지한다. 너무 많은 재귀함수 호출은

스택오버플로우를 발생시킨다. 그러므로 메모리의 효율적 관리를 위해 재귀함수가 아닌 다른 방법으로 퀵정렬을 시도해보겠다.

 

스택(Stack)을 이용한 퀵정렬

 

퀵정렬은 pivot보다 작은 구간과 큰 구간으로 나눈 후 다시 퀵정렬을 구간별로 진행하는 방식이다. 재귀는 pLeft와 pRight를 매개변수의 인수로 받아 퀵정렬을 하였다. 재귀를 사용하지 않을거면 pLeft와 pRight를 저장할 별도의 공간이 필요하다.

 

우리는 그 공간으로 Stack을 사용할 것이다.

 

 

 

 

길이가 8인 배열이다. pLeft와 pRight는 0과 8이고 pivot은 2이다. 두 가지 스택을 만든다. 하나는 pLeft 용 스택, 다른 하나는 pRight용 스택이다. 첫 pLeft와 첫 pRight의 값은 배열은 처음과 끝인 0과 8이다. 첫 시작은 아래와 같다.

 

 

이제 배열을 pivot인 2보다 작은 구간과 큰 구간으로 나눈다.

 

 

이렇게 구간이 나누어지면 구간별로 퀵정렬을 해야한다. 이를 위해, 각 구간의 pLeft와 pRight를 Stack에 저장한다.

 

 

 

Stack에서 pop()하여 얻은 구간 좌표를 퀵정렬을 진행하는 방식이다. 퀵정렬을 진행할수록 구간이 더 나누어지므로 Stack도 쌓여져간다. 이런 반복은 Stack이 모두 비워졌을때까지 진행된다.

 

 

코드

 

public static void quickSortStack(int left, int right) {
		Stack<Integer> leftStack = new Stack<Integer>(); //pLeft용 스택생성
		Stack<Integer> rightStack = new Stack<Integer>(); //pRight용 스택생성
		
		leftStack.push(left); // 첫 pLeft값 push
		rightStack.push(right); // 첫 pRight값 push
		
		while(!leftStack.isEmpty()) { // 스택이 비워질때까지 반복
        
			int pLeft = left = leftStack.pop(); // pLeft값 pop
			int pRight = right = rightStack.pop(); // pRight값 pop
			int pivot = arr[(left+right)/2]; // pivot 구하기
			
            		// 퀵정렬 알고리즘
			do {
				while(arr[pLeft] < pivot ) pLeft++;
				while(arr[pRight] > pivot ) pRight--;
				
				if(pLeft <= pRight) {
					swap(pLeft++,pRight--);
				}
			}while(pLeft <= pRight);
		
        		// pivot보다 작은 구간 Stack에 push
			if(left < pRight) {
				leftStack.push(left);
				rightStack.push(pRight);
			}
            		// pivot보다 큰 구간 Stack에 push
			if(pLeft < right ) {
				leftStack.push(pLeft);
				rightStack.push(right);
			}
		}	
	}