[알고리즘] 퀵 정렬 Java

퀵 정렬은 가장 빠른 정렬 알고리즘 중의 하나로 시간 복잡도는 평균적으로 O(nlog n)입니다.

 

퀵 정렬 예시

public class Main {
    
    public static void main(String[] args) {
        
        int data[] = {1,5,9,7,6,4,23};
        
        quickSort(data, 0, data.length - 1);
        for(int i=0; i<data.length; i++){
            System.out.println("data["+i+"] = "+data[i]);
        }
    }

    public static void quickSort(int[] data, int l, int r){
        int left = l;
        int right = r;
        int pivot = data[(l+r)/2];
        
        do{
            while(data[left] < pivot) left++;
            while(data[right] > pivot) right--;
            if(left <= right){    
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        }while (left <= right);
        
        if(l < right) quickSort(data, l, right);
        if(r > left) quickSort(data, left, r);
    }
}