Algorithm ‐ Quick Sort - dnwls16071/Backend_Study_TIL GitHub Wiki

📚 Quick Sort

public static void sortByQuickSort(int[] arr) {
    // 배열 전체 범위에 대한 퀵 정렬을 시작한다.
    quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int left, int right) {
    int part = partition(arr, left, right);

    // 처음 시작 인덱스가 분할 지점보다 작은 경우 재귀를 돌리기
    if (left < part - 1) {
        quickSort(arr, left, part - 1);
    }
   
    // 마지막 종료 인덱스가 분할 지점보다 큰 경우 재귀를 돌리기
    if (right > part) {
        quickSort(arr, part, right);
    }
}

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[(left + right) / 2];
    while (left <= right) {
        
        // 왼쪽에서부터 피벗보다 큰 값을 찾는다.
        while (arr[left] < pivot) {
            left++;
        }

        // 오른쪽에서부터 피벗보다 작은 값을 찾는다.
        while (arr[right] > pivot) {
            right--;
        }

        // 역전되지 않았다면 Swap으로 값을 교체
        if (left <= right) {
            swap(arr, left, right);
            left++;
            right--;
        }
    }

    // 처음 시작 인덱스를 반환
    return left;
}

• left : 부분 배열의 왼쪽 인덱스
• right : 부분 배열의 오른쪽 인덱스
• pivot : 피벗(여기선 중간 위치로 설정)