퀵 정렬로 풀기 Quick Sort

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
	public static ArrayList<Integer> array_split(ArrayList<Integer> array){
		if (array.size()<=1) {
			return array;
		}
        int pivot_index = array.size()/2;
        ArrayList<Integer> pre = new ArrayList<>(); //pivot보다 작은 원소들이 들어갈 벡터
        ArrayList<Integer> post = new ArrayList<>(); //pivot보다 큰 원소들이 들어갈 벡터
        for (int j=0; j<array.size(); j++){
            if (j == pivot_index){
                continue;
            }
            
            if(array.get(j)<array.get(pivot_index)){
            	
                pre.add(array.get(j));
            }
            
            else{
                post.add(array.get(j));
            }
        }
        
        if ((pre.size()<2) && (post.size()<2)){
            //정렬 완료
            pre.add(array.get(pivot_index));
            pre.addAll(post);
            return pre; //다 합쳐서 리턴
        }
        //pre, post 각자 정렬
        pre = array_split(pre); //완벽히 정렬된채로 리턴(위의 조건식)
        post = array_split(post);


        pre.add(array.get(pivot_index));
        pre.addAll(post);
        return pre; //다 합쳐서 리턴

    }
    
    
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
	    int array_size = scan.nextInt();
	    ArrayList <Integer> array = new ArrayList<>();
	    ArrayList <Integer> new_array = new ArrayList<>();

	    for (int i=0; i<array_size; i++){
	        int num = scan.nextInt();
	        array.add(num);
	    }
		new_array = array_split(array);
	    for (int i=0; i<new_array.size(); i++){
	        System.out.println(new_array.get(i));
	    }    
	    scan.close();
	}//main

}

주의

if (array.size()<=1) {
	return array;
}

이 부분을 안 썼더니 IndexOutOfBounds 에러가 난다.
왜냐면 매개변수로 들어온 array가 size가 0인 경우 array.get(j)를 하면 outofrange
아니근데 어차피 size가 0이면 for문이 실행이 안 되잖아 뭔 상관이야?

for문 말고 그 뒤에서 오류가 남..

array가 아예 비어있는 애한테 31줄의 get(0)을 하면 error가 남.

if ((pre.size()<2) && (post.size()<2))

이거는 pre와 post랑 pivot 합친 게 완벽하게 정의됐을 때고 만약 pre는 원소가 1개나 0개인데 post는 원소가 여러개면 그건 post쪽은 정의되지 않은 거니까 여기서 return이 안 되고 (내가 처음 코드를 짤 때 이런 비대칭적인 건 생각을 못 했음 한 쪽의 arrayList의 원소가 1개나 0개면 여기서 걍 다 return 된다고 퉁쳤나봄 왜저래)

//pre, post 각자 정렬
        pre = array_split(pre); //완벽히 정렬된채로 리턴(위의 조건식)
        post = array_split(post);

가 실행이 됨. 이 때 post는 몰라도 pre는 원소가 1개거나 0개인데 또 호출하게 되면 비효율적. 따라서 1개거나 0개일 때는 예외로

if (array.size()<=1) {
	return array;
}

이걸 써주는 게 맞음