[자료구조] 퀵정렬 (Java)

퀵정렬은  값을 다른 원소와 비교만으로 정렬을 수행하는 비교 정렬이다.

 

퀵정렬은 분할정복 알고리즘중 하나로 평균 수행속도가 빠르다.

 

분할정복이란?

분할 정복은 하나의 문제를 2개의 문제로 분리하여서 해결한 다음 하나로 모아서

원래의 문제를 해결하는 전략이다.

 

그렇담 퀵정렬에서는 분할정복 방식이 어떻게 적용이 되는지 알아보자.

 

 

 

퀵정렬 과정

 

1. 배열안의 한 요소를 선택한다.

 

2. 여기서 고른 원소는 pivot(피봇)이라고 한다.

 

3. 피봇을 기준으로 피봇보다 작은쪽은 모두 왼쪽으로 옮기고

피봇보다 큰쪽은 피봇의 오른쪽으로 옮긴다.

 

4. 그렇게 나뉜 피벗을 기준으로 파티션을 나눠서 또다시

위와 같은 방식으로 파티션이 한개가 되기전까지 분류를 한다.

 

 

그래서 이처럼 크기가 1이될때까지 계속해서 분할하기 때문에

시간복잡도는 O(n log n)이 된다.

 

그럼 좀 더 구체적으로 예제를 보면서 하자.

 

아래와 같이 배열이 주어 지고 start end는 시작과 끝을 가르키게 한다.

위 상황에서 start는 점점 증가해서 올라오는데 그 조건은 pivot인 7보다 작을때이다.

그리고 end는 점점 감소해서 내려온다. 그리고 그 조건은 pivot인 7보다 클때이다.

 

그럼 아래 상황에서 서로 멈추게 된다.

위 상황에서 각자 멈추면 start와 end의 값을 서로 바꿔주고 start와 end의 index를 이동시킨다.

 

그럼 이제 다시 start와 end가 start < pivot , end > pivot이 될때까지 서로의 index를 이동시켜주자.

그럼 아래의 상황에서 또다시 멈추게 된다.

 

 

그럼 또다시 서로를 바꿔주고 index를 이동시키고 다시 확인을 한다.

 

다음 단계로 넘어가서 둘의 위치도 서로 바꿔줘야 한다.

 

그러고 나서 start가 end보다 커지게 되면 그제서야 파티션 나누는걸 멈춘다.

이렇게 파티션 나누는걸 멈추면 start의 index를 return 해서 또다시 

 

0 -> start-1

 

start < arr.length-1

 

저둘을 나눠서 똑같이 위와 같은 방식으로 정렬을 해준다.

 

위의 상황을 소스로 보면 아래와 같다.

	//오버로딩한 다른 quiㅏSort() 호출
	public void quikSort(int[] arr) {
		quikSort(arr, 0, arr.length-1);
	}

	//여기서는 파티션을 나누고 그 나눈 파티션을 가지고 다시 quikSort를 재귀호출한다.
	private void quikSort(int[] arr, int start, int end) {
		// TODO Auto-generated method stub
		int part2 = part(arr,start, end); //나뉜 부분의 시작 index를 받는다.
		
		if(start < part2 - 1) { //하나만 잘려서 만들어진 애는 quikSort하면 안되기 때문
			quikSort(arr,start,part2 - 1); //재귀호출을 해서 하나만 나올때까지 계속함
			//시작위치 전까지 sort해야함
		}
		if(part2 < end) {
			quikSort(arr,part2,end);
		}
	}

	//피봇을 기준으로 파티션을 나누는 부분
	private int part(int[] arr, int start, int end) {
		// TODO Auto-generated method stub
		int pivot = arr[(start + end) / 2];
		while(start <= end) {
			while(arr[start]<pivot) {
				start++;
			}
			while(arr[end]> pivot) {
				end--;
			}
			if(start <= end) { //index들이 서로를 지나치지 않았을때 진입
				swap(arr,start,end);
				start++;
				end--;
			}
		}
		
		return start;
	}

	//start index에 있는 수와 end index에 있는 수를 서로 바꿔줌.
	private void swap(int[] arr, int start, int end) {
		// TODO Auto-generated method stub
		int temp = arr[start];
		arr[start] = arr[end];
		arr[end] = temp;
	}

 

 

위의 소스에서 

if(start < part2 - 1) 와 if(part2 < end)를 하는 이유는 파티션을 나눴을때 아래와 같이 나왔을때

 

저렇게 하나로 이미 나눠진 부분은 다시 정렬할 필요가 없기 때문에 위의 상황이 아닐때만 다시 재귀호출하게 

한것이다.

 

 

※주의사항

1. 서로의 값을 바꿔줄때 start와 end가 서로 지나치지 않았는지 확인하고

start와 end의 꼭 index를 증가시키자. ( 안그러면 무한반복 된다.)

ex)

			if(start <= end) { //index들이 서로를 지나치지 않았을때 진입
				swap(arr,start,end);
				start++;
				end--;
			}

 

2. 다시 quikSort를 재귀 호출할때는 

파티션의 시작 부분 - 1까지 부분을 정렬해야한다.

		if(start < part2 - 1) { //하나만 잘려서 만들어진 애는 quikSort하면 안되기 때문
			quikSort(arr,start,part2 - 1); //재귀호출을 해서 하나만 나올때까지 계속함
			//시작위치 전까지 sort해야함
		}