JAVA 알고리즘 - Quick 정렬 구현하기

업무 중, 퀵정렬을 사용할 경우가 생겨서 리마인드 할 겸, 정리해서 작성해 보았다.

매일 매일 사용하면 까먹지라도 않겠지... 리마인드 하면서 머리속에 세뇌시켜야지..

public class QuickSortRemind {
	public static void main(String[] args) {
		
		// test 데이터
		int[] arr = {22,5,7,33,4,55,88,22,553,67,2,7,9,10};
		
		// quickSort 함수 호출
		// 0부터 배열 length 까지 탐색
		quickSort(arr, 0, arr.length-1);
		
		// 출력
		for ( int a : arr ) {
			System.out.println(a);
		}
	}
	
	static void quickSort(int[] arr, int start, int end) {
		// 퀵소트는 중간값에서 파티션을 양쪽으로 나눠서 값을 비교하고 swap 한다. ( 파티션1 | 피봇(중간값) | 파티션2 )
		// partition 의 return 값 part는 파티션1의 마지막 end 값
		// partition 의 return 값 part는 파티션2의 첫번째 start 값
		int part = partition(arr, start, end); // 중간 값 index 도출
		// start 값과 파티션1의 마지막 end 값으로 비교
		// start는 0부터 시작~ 
		if( start < part-1 ) {
			
			// 재귀함수 호출
			quickSort( arr, start, part-1 );
		}
		
		// 마지막 end 값과 파티션2의 첫번째 start 값으로 비교
		if ( end > part ) {
			
			// 재귀함수 호출
			quickSort( arr, part, end );
		}
	}
	
	static int partition(int[] arr, int start, int end) {
		
		// start + end / 2로 중간값 인덱스를 찾을 수 있다.
		int pivot = arr[ (start+end) / 2]; // 중간 값 pivot 추출
		// start 시작값이 end 값보다 작거나 같을 때까지 loop
		while ( start <= end ) {
			// 피봇 ( 중간값 )이 start 인덱스 배열값보다 작으면 swap 할 필요가 없으니 start 값을 ++ 한다.
			while ( arr[start] < pivot ) {
				start++;
			}
			// 피봇 값이 end 인덱스 배열의 값보다 크면 swap 할 필요가 없으니 끝에서부터 -- 한다.
			while ( arr[end] > pivot ) {
				end--;
			}
			// start가 end 값보다 작거나 같을 때.
			if ( start <= end ) {
				// swap 진행 
				// why ? -> start 값과 end 값은 위 while 문에서 변경해야 할 인덱스 값으로 삽입된다.
				// start end 값 비교가 필요 없을 경우 while문을 종료한다.
				swap(arr, start, end);
				start++;
				end--;
			}
		}
		return start;
	}
	
	// 배열 스왑
	static void swap (int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}