[C++] HeapSort vs BubbleSort

Sung_1·2023년 8월 5일

C cpp

C++

목록 보기

2/2

HeapSort의 시간 복잡도는 O(nlogn)이고, BubbleSort의 시간 복잡도는 O(n^2)이다.
차이가 얼마나 나는지 실험해봤다.

시간을 측정하기 위해 clock() 함수를 이용하였다. 시간을 측정하는 함수는 다음과 같다.

시간 측정 함수

void clock_check(int opt){
    if(opt == 0){
        start=clock();
    }
    else{
        finish = clock();
        duration = double(finish - start) / CLOCKS_PER_SEC;
        cout<<"time : "<<duration<<"\n";
    }
}

opt가 0이면 시간 측정을 시작하고, 1이면 시간 측정을 종료하고 동작이 끝나기까지 걸린 시간을 초 단위로 출력한다.

여기서는 오름차순 정렬을 기준으로 코드를 작성했다.

min_heap의 코드이다 vector를 사용해서 구현하였다.

HeapSort 코드

class min_Heap {
private:
    vector<int> v;

public:
    min_Heap() {
        v.push_back(-99); // for dummy_value.
    }

    void up_heap(int index) {
        while (index > 1 && v[index / 2] > v[index]) {
            swap(v[index / 2], v[index]);
            index = index / 2;
        }
    }

    void insert_node(int val) {
        v.push_back(val);
        up_heap(v.size() - 1);
    }

    void downHeap(int index) {
        int left = index * 2;
        int right = index * 2 + 1;
        int size = v.size();
        int smallestChild = index;

        if (left < size && v[left] < v[index]) { // 왼쪽 자식만 있는 경우
            smallestChild = left;
        }


        if (right < size && v[right] < v[smallestChild]) {
            smallestChild = right;
        }

        if (smallestChild != index) {
            swap(v[smallestChild], v[index]);
            downHeap(smallestChild);
        }
    }

    int pop() {
        int min_value = v[1];
        swap(v[1], v[v.size() - 1]);
        v.pop_back();
        downHeap(1);
        return min_value;
    }

    void print_All() {
        clock_check(0);
        while (v.size() > 1) {
            int top = pop();
            cout << top << " ";
        }
        clock_check(1);
        cout << "\n";
    }
};

bubbleSort 코드 및 출력 함수

void bubble_sort(int *arr,int size){
    clock_check(0);
    for(int i = 0;i < size; i++){
        for(int j = i; j < size; j++){
            if(arr[i] > arr[j]){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    clock_check(1);
}
void print_Array(int *arr,int size){
    for(int i = 0; i < size; i++)
        cout<<arr[i]<<" ";
    cout<<"\n";
}

대망의 메인함수이다.

메인 함수

int main(){
    int size = 100000;

    int *arr = new int[size];
    min_Heap minHeap;

    srand(time(NULL));
    for(int i = 0; i < size; i++){
        int input = rand() % 10000000;
        arr[i] = input;
        minHeap.insert_node(input);
    }
    //bubble_sort
    cout<<"input size = " << size<<"\n";
    cout<<"------------------ <bubble sort> ------------"<<"\n";
    bubble_sort(arr,size);
    cout<<"------------------ <heap sort> ------------"<<"\n";
    minHeap.print_All();
}