Implement Quick Sorting

퀵 정렬 구현

import java.util.Arrays;

public class Main3 {

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right){
            return;
        }

        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot -1 );
        quickSort(arr, pivot + 1, left);

    }

    public static int partition(int[] arr, int left, int right) {
    	// 가장 좌측 값을 기준값으로 설정
        // 이외에 기준 값은 배열에서 중간에 있는 값을 고르거나,
        // 임의의 수를 3개 선정 후 중앙 값을 고르는 등의 방법이 있다.
        int pivot = arr[left];
        int i = left;
        int j = right;
        
		// left에서 시작하여 pivot보다 큰 값을 찾는 과정
        while (i < j){
            while (arr[i] <= pivot && i < j){
                i++;
            }
            
        // right에서 시작하여 pivot보다 작은 값을 찾는 과정    
            while (arr[j] > pivot && i < j){
                j--;
            }
		
        // 두 값을 정렬
            swap(arr, i, j);
        }
		// i 와 j가 만난 지점에서 pivot 지점과 정렬
        swap(arr, left, i);

        return i;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("퀵 정렬: " + Arrays.toString(arr));
    }
}

//출력
퀵 정렬: [2, 4, 5, 6, 7, 8, 9]