퀵 소트

import java.util.Scanner;

public class Main2 {	
	
	static int[] arr = new int[100];
	
	static public void quickSort(int st, int ed) {
		// ex) arr = [3, 1, 4]
		// [0]을 pivot으로 잡아서 왼쪽에는 pivot보다 작은 값 오른쪽에는 pivot보다 큰 값 세팅
		// pivot보다 작은 왼쪽 리스트와 큰 오른쪽 리스트 두 개로 나뉨 리스트가 1이 될때까지 반복
		// 왼쪽 리스트는 pivot보다 작은 수들의 집합이지만 그 안에서 정렬이 안되어 있기 때문에 정렬이 되어 있는 최소단위인 1까지 반복해야 함
		
		// ex) arr =[3] 데이터가 하나 있는 경우는 재귀적으로 반복하지 않고 그냥 출력
		if(ed <= st+1) return; // base condtion(재귀 함수 탈출 조건)
		int pivot = arr[st];
		int lIndex = st + 1;
		int rIndex = ed - 1;
		while(true) {			
			// pivot 왼쪽에 있는 리스트들은 pivot보다 작은 값들이 와야하므로 pivot 보다 큰 값이 있으면 해당 인덱스에서 멈춤
			while(lIndex <= rIndex && arr[lIndex] <= pivot) lIndex++;			
			// pivot 오른쪽에 있는 리스트들은 pivot보다 큰 값들이 와야하므로 pivot 보다 작거나 같은 값이 있으면 해당 인덱스에서 멈춤
			while(lIndex <= rIndex && arr[rIndex] >= pivot) rIndex--;
			
			if(rIndex > lIndex) break;
			// pivot을 기준으로 왼쪽 오른쪽 swap
			int tmp = arr[rIndex];
			arr[rIndex] = arr[lIndex];	
			arr[lIndex] = tmp;			
		}
		// rIndex가 lIndex보다 작아질 때 pivot과 rIndex의 값 swap
		int tmp = arr[st];
		arr[st] = arr[rIndex];	
		arr[rIndex] = tmp;
		quickSort(st, rIndex);
		quickSort(rIndex+1, ed);
	}	
	
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for(int i=0;i<n;i++) {
			arr[i] = sc.nextInt();
		}
		quickSort(0, n);
		for(int i=0;i<n;i++) {
			System.out.println(arr[i]);
		}
	}

}