🚀 힙 정렬과 퀵 정렬 비교하기

힙 정렬과 퀵 정렬 모두 평균 시간복잡도는 O(nlogn)으로 동일합니다
하지만 실제 실행 시간을 비교해보면 퀵 정렬이 더 빠른 성능을 나타냅니다

import java.io.*;  
import java.util.*;  

class HeapSort{  
  
    public static void heapSort(int[] arr){  
        if(arr.length < 2){  
            return;  
        }  
        int parent = ((arr.length-1)-1) / 2;  
  
        for (int i = parent; i >= 0; i--) {  
            heapify(arr, i, arr.length-1);  
        }  
  
        for (int i = arr.length-1; i > 0; i--) {  
            swap(arr, 0, i);  
            heapify(arr, 0, i-1);  
        }  
  
    }  
  
  
    private static void heapify(int[] arr, int parent, int last){  
        int left = 2 * parent + 1;  
        int right = 2 * parent + 2;  
        int large = parent;  
  
        if(left <= last && arr[left] > arr[large]){  
            large = left;  
        }  
  
        if(right <= last && arr[right] > arr[large]){  
            large = right;  
        }  
  
        if(parent != large){  
            swap(arr, large, parent);  
            heapify(arr, large, last);  
        }  
  
    }  
  
  
    private static void swap(int[] arr, int a, int b){  
        int tmp = arr[a];  
        arr[a] = arr[b];  
        arr[b] = tmp;  
    }  
  
}  
  
  
public class Main {  
    private static void quickSort(int[] arr, int left, int right) {  
        if(left < right){  
            int pivot = partition(arr, left, right);  
            quickSort(arr, left, pivot-1);  
            quickSort(arr, pivot+1, right);  
        }  
    }  
  
    private static int partition(int[] arr, int left, int right) {  
        int pivot = arr[right];  
        int l = left - 1;  
        for (int i = left; i < right; i++) {  
            if(arr[i] <= pivot){  
                l++;  
                swap(arr, l, i);  
            }  
        }  
        swap(arr, l+1, right);  
        return l+1;  
    }  
  
    private static void swap(int[] arr, int l, int r){  
        int tmp = arr[l];  
        arr[l] = arr[r];  
        arr[r] = tmp;  
    }  
  
    public static void main(String[] args) {  
        int size = 100_000; // 배열 크기 (필요에 따라 조정)  
        int[] originalArray = new int[size];  
        Random rand = new Random();  
  
        for (int i = 0; i < size; i++){
        	originalArray[i] = rand.nextInt();  
        }
  
        // 힙 정렬 테스트  
        int[] arr1 = Arrays.copyOf(originalArray, size);  
        long heapStart = System.nanoTime();  
        HeapSort.heapSort(arr1);  
        long heapEnd = System.nanoTime();  
  
        System.out.printf("Heap Sort 소요 시간: %.3f ms\n", (heapEnd - heapStart) / 1_000_000.0);  
  
        // 퀵 정렬 테스트  
        int[] arr2 = Arrays.copyOf(originalArray, size);  
        long quickStart = System.nanoTime();  
        quickSort(arr2, 0, size - 1);  
        long quickEnd = System.nanoTime();  
  
        System.out.printf("Quick Sort 소요 시간: %.3f ms\n", (quickEnd - quickStart) / 1_000_000.0);  
    }  
}

위와 같이 코드를 구현해, 힙정렬과 퀵정렬의 실행시간을 비교했습니다

총 5번을 반복해서 소요시간을 측정한 결과, 다음과 같은 결과가 나왔습니다

- heap sort 평균 소요시간: 21.956 ms
- quick sort 평균 소요시간: 18.967 ms

일반적으로 평균 소요시간이 Quick Sort가 더 빠른 것을 확인할 수 있습니다

✍️ 결론

두 알고리즘은 이론상 동일한 시간복잡도를 가지지만, 실제로는 퀵 정렬이 평균적으로 더 빠릅니다

따라서 빠른 정렬이 필요한 상황에서는 퀵 정렬을 사용하는 것이 좋습니다
하지만 퀵 정렬은 피벗 선택이 좋지 않을 경우 최악의 시간복잡도 O(n²)로 성능이 저하될 수 있기 때문에,
안정적인 성능이 필수적인 경우에는 힙 정렬이나 병합 정렬 같은 다른 알고리즘을 선택하는 것이 권장됩니다