퀵 정렬( Quick Sort ) 알고리즘

 

public class QuickSortTest {

	private void quickSort2(int[] arr, int start, int end) {
		int part2 = partition(arr , start , end); //분할
		if(start < part2 -1 ) { 
			quickSort2(arr, start, part2-1);
		}
		if(part2 <  end) {
			quickSort2(arr, part2, end); 
		}
	}
    
    private int partition(int[] arr, int start, int end) {
		int pivot = arr[(start + end) / 2];
		while(start <= end) {
			while(arr[start] < pivot) {
				start++;
			}
			while(arr[end] > pivot) {
				end--;
			}
			if(start <= end ) {
				swap(arr , start , end);
				start++;
				end--;
			}
		}
		return start;
	}



	private void swap(int[] arr, int startPoint, int endPoint) {
		int p = 0;
		p = arr[startPoint];
		arr[startPoint] = arr[endPoint];
		arr[endPoint] = p;
		
	}
    
    	public static void main(String[] args) {
		QuickSortTest qs = new QuickSortTest();
		int [] arr = {3,9,4,7,5,0,1,6,8,2};
		
        //퀵정렬 전
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		
        qs.quickSort2(arr , 0 , arr.length -1);
		
        //퀵정렬 후
        System.out.println();
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
    
    

}

 

 

결과 :