퀵정렬

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class 퀵정렬 {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int arr[] = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}
		
		for (int i : new 퀵정렬().solution(n, arr)) {
			System.out.print(i + " ");
		}
		
	}
	
	public List<Integer> solution(int n, int[] arr) {
		List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
		return quickSort(list);
	}
	
	public List<Integer> quickSort(List<Integer> list) {
		if (list.size() <= 1) return list;
		
		List<Integer> leftList = new ArrayList<Integer>();
		List<Integer> centerList = new ArrayList<Integer>();
		List<Integer> rightList = new ArrayList<Integer>();
		
		int pivot = list.get(list.size() / 2);
		for (int i = 0; i < list.size(); i++) {
			if (pivot > list.get(i)) 		leftList.add(list.get(i));
			else if (pivot < list.get(i)) 	rightList.add(list.get(i));
			else 							centerList.add(list.get(i));
		}
		
		List<Integer> resultList = new ArrayList<Integer>();
		resultList.addAll(quickSort(leftList));
		resultList.addAll(quickSort(centerList));
		resultList.addAll(quickSort(rightList));
		
		return resultList;
	}
}