QuickSort.java

package test;

import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
//		int[] arr = {6, 3, 2, 7, 1, 5, 0, 9, 8, 4};
		int[] arr = new int[10];
		for(int i = 0 ; i < arr.length ; i++) {
			arr[i] = (int)(Math.random() * 101);
		}
		
		System.out.println(Arrays.toString(arr));
		System.out.println();
		
		quickSort(arr, 0, arr.length - 1);
		
		System.out.println();
		System.out.println(Arrays.toString(arr));
	}
		
	private static void quickSort(int[] arr, int lo, int hi) {
		if(lo >= hi) return;
		
		System.out.println("▶ pivot : " + arr[lo] + ", lo : " + lo + ", hi : " + hi);
		int pivot = partition(arr, lo, hi);
		System.out.println("▶ 결과 " + Arrays.toString(arr));
		System.out.println();
		
		quickSort(arr, lo, pivot - 1);
		quickSort(arr, pivot + 1, hi);
	}
	
	private static int partition(int[] arr, int left, int right) {
		int lo = left;
		int hi = right;
		int pivot = arr[left];
		
		while(lo < hi) {
			System.out.print("  hi : ");
			while(arr[hi] > pivot && lo < hi) {
				System.out.print(arr[hi] + "(" + hi + ") ");
				hi--;
			}
			System.out.print(arr[hi] + "(" + hi + ") ");
			System.out.println();
			
			System.out.print("  lo : ");
			while(arr[lo] <= pivot && lo < hi) {
				System.out.print(arr[lo] + "(" + lo + ") ");
				lo++;
			}
			System.out.print(arr[lo] + "(" + lo + ") ");
			System.out.println();
			
			System.out.println("  swap   ▷ " + arr[lo] + "(" + lo + ")" + " ↔ " + arr[hi] + "(" + hi + ")");
			System.out.println("  swap 전 ▷ " + Arrays.toString(arr));
			swap(arr, lo, hi);
			System.out.println("  swap 후 ▷ " + Arrays.toString(arr));
			System.out.println();
		}
		System.out.println("▶ swap " + arr[left] + "(" + left + ")" + " ↔ " + arr[lo] + "(" + lo + ")");
		swap(arr, left, lo);

		return lo;
	}
	
	private static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}