퀵 정렬

퀵 정렬 

레코드의 자료 이동을 최소화하며 배열을 정렬하는 퀵 정렬은 선택한 피벗을 중심으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 정렬하는 방식입니다. 피벗을 정하고, 작은 값은 피벗 왼쪽으로, 큰 값은 오른쪽으로 이동시키는 과정을 반복하며 서브 파일을 만들어 나가며 정렬합니다. 이 재귀적 분할 정복 과정을 통해 전체 배열을 정렬합니다.

정렬 과정

정복

분할된 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다. 이는 각 부분 배열에 대해 위의 과정을 반복하는 것을 의미합니다. 각 부분배열은 피벗을 기준으로 다시 분할되고 정렬됩니다.

public void quickSort(int[] array, int left, int right) {
    if(left >= right) return;
    
    // 분할 
    int pivot = partition(); 
    
    quickSort(array, left, pivot-1);  // 정복(Conquer)
    quickSort(array, pivot+1, right); // 정복(Conquer)
}

분할

피벗을 선택합니다. 피벗은 배열에서 하나의 요소를 선택하는 것인데, 이 값에 따라 배열이 분할, 정렬됩니다. 피벗 선택에 따라 퀵 정렬의 성능이 좌우됩니다.

선택한 피벗을 기준으로 배열을 두 그룹으로 나눕니다. 피벗보다 작은 요소는 피벗 왼쪽에 오도록 배치하고, 큰 요소는 오른쪽에 배치합니다. 즉 피벗을 중심으로 배열을 분할하여 작은 값과 큰 값을 나누는 과정입니다.

public int partition(int[] array, int left, int right) {
    
    int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
    int i = left, j = right;
    
    while(i < j) {
        while(pivot < array[j]) {
            j--;
        }
        while(i < j && pivot >= array[i]){
            i++;
        }
        swap(array, i, j);
    }
    array[left] = array[i];
    array[i] = pivot;
    
    return i;
}

퀵정렬 장/단점

퀵 정렬은 요소 이동 횟수가 적어 다른 알고리즘에 비해 빠른 성능을 보여줍니다. 또한 추가 메모리를 사용하지 않고 배열 내에서 작업하기 때문에 공간 효율성도 높습니다. 다만 이미 정렬된 배열이나 특정한 패턴의 배열에서는 성능이 급격하게 저하될 수 있는 단점이 있습니다.