정렬,머지소트,퀵소트 C++ 코드

 

#정렬속도 비교

 

알고리즘	최선 수행시간	평균 수행시간	최악 수행시간	Run-time(정수 60,000개, 단위sec)
삽입 정렬	O(n)	O(n2)	O(n2)	7.438
선택 정렬	O(n2)	O(n2)	O(n2)	10.842
버블 정렬	O(n2)	O(n2)	O(n2)	22.894
카운팅 정렬	O(n2)	O(n+k)	O(n+k)	.
Shell 정렬	O(n)	O(n1.5)	O(n2)	0.056
퀵 정렬	O(n log n)	O(n log n)	O(n2)	0.014
병합 정렬	O(n log n)	O(n log n)	O(n log n)	0.026
힙정렬	O(n log n)	O(n log n)	O(n log n)	0.034

 

#머지소트

#include <iostream>
#include <vector>

// 함수 선언
std::vector<int> merge_sort(const std::vector<int>& Data);
std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right);

// Merge Sort 함수 정의
std::vector<int> merge_sort(const std::vector<int>& Data) {
    if (Data.size() <= 1) {
        return Data;
    }

    int mid = Data.size() / 2;
    std::vector<int> left(Data.begin(), Data.begin() + mid);
    std::vector<int> right(Data.begin() + mid, Data.end());

    left = merge_sort(left);
    right = merge_sort(right);

    return merge(left, right);
}

// Merge 함수 정의
std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right) {
    std::vector<int> result;
    int i = 0, j = 0;

    while (i < left.size() && j < right.size()) {
        if (left[i] < right[j]) {
            result.push_back(left[i]);
            i++;
        } else {
            result.push_back(right[j]);
            j++;
        }
    }

    while (i < left.size()) {
        result.push_back(left[i]);
        i++;
    }

    while (j < right.size()) {
        result.push_back(right[j]);
        j++;
    }

    return result;
}

// 메인 함수 정의
int main() {
    std::vector<int> Data = {38, 27, 43, 3, 9, 82, 10};
    std::vector<int> sorted_Data = merge_sort(Data);

    for (int num : sorted_Data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

#퀵소트

#include <iostream>
#include <vector>

std::vector<int> Data = {3, 2, 4, 6, 9, 1, 8, 7, 5};

void Quick_sort(int _from, int _to);
int partition(int left, int right);

void Quick_sort(int _from, int _to) {
    if (_from < _to) {
        int pivot = partition(_from, _to);
        Quick_sort(_from, pivot - 1);
        Quick_sort(pivot + 1, _to);
    }
}

int partition(int left, int right) {
    int where = left;
    int pivot = Data[where];
    while (left < right) {
        while (left < Data.size() && Data[left] <= pivot) {
            left++;
        }
        while (Data[right] > pivot) {
            right--;
        }
        if (left < right) {
            std::swap(Data[left], Data[right]);
        }
    }
    std::swap(Data[where], Data[right]);
    return right;
}

int main() {
    Quick_sort(0, Data.size() - 1);
    for (int num : Data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}