[정렬] 4.퀵정렬 (Quick Sort)

public class QuickSort {
	public static void main(String args[]){
		int array[] = {10, 87, 2, 42, 51, 12, 5, 29, 78, 50};
		
		//quicSort(배열, 배열첫번째인자(0), 배열마지막인자(9))
		Sort.quickSort(array, 0 ,array.length-1);
		
		//정렬된 배열 출력
		for(int num : array){
			System.out.print(num+" ");
		}
	}
}

public class Sort {

	// 퀵정렬 : 기준값(pivot)과 비교해 작은수는 왼쪽 큰수는 오른쪽으로 분할을 하고 분할 된 배열들을 재귀함수를 이용해서 똑같이 분할 정렬한다.
	public static void quickSort(int array[], int row, int high) {
		// 비교 할 데이터가 2개 이상일때 실행
		if (row < high) {
			int pivot = partition(array, row, high);
			quickSort(array, row, pivot - 1); //기준값의 왼쪽 수들 정렬
			quickSort(array, pivot + 1, high); // 기준값의 오른쪽 수들 정렬
		}
	}

	public static int partition(int array[], int row, int high) {
		int p_val = array[row];
		int pivot = row;

		for (int i = row + 1; i <= high; i++) {

			if (p_val > array[i]) {
				swap(array, ++pivot, i);
			}
		}
		swap(array, row, pivot);
		return pivot;
	}

	public static void swap(int array[], int pivot, int i) {
		int temp = array[i];
		array[i] = array[pivot];
		array[pivot] = temp;
	}
}