Insertion Sort

#include <iostream>
#include <chrono>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

vector<int> randomVector(int n) {
    vector<int> vec(n);
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        vec[i] = rand() % 100;
    }
    return vec;
}


void insertionSort(vector<int>& array, int n) {
    int i, j;
    for (i = 1; i < n; i++) {
        int key = array[i];
        j = i - 1;
        for (j = i - 1; j >= 0; j--) {
            if (array[j] > key) {
                array[j + 1] = array[j];
            }
            else{
                break;
            }
        }
        array[j + 1] = key;
    }
}
void checkSort(vector<int>& a, int n) {
    int i;
    bool sorted = true;
    for (i = 0; i < n-1; i++) {
        if (a[i] > a[i + 1]) {
            sorted = false;
        }
        if (!sorted) {
            break;
        }
    }
    if (sorted) {
        cout << "정렬 완료.\n";
    }
    else {
        cout << "정렬 오류.\n";
    }
}

int main() {
    int n = 10;
    vector<int> vec = randomVector(n);
    cout << "Random Vector: ";
    for (int i = 0; i < n; i++) {
        cout << vec[i] << " ";
    }
    auto start = chrono::high_resolution_clock::now();
    insertionSort(vec,n);
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end - start;
    cout << "\nSorted Vector: ";
    for (int i = 0; i < n; i++) {
        cout << vec[i] << " ";
    }
    cout << endl;
    checkSort(vec, n);
    cout << "Runtime: " << duration.count() << " seconds." << endl;
    return 0;
}

n = 10인 배열에서 삽입 정렬을 확인했습니다.

Shell Sort

Gap Sequence N/2

#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

vector<int> randomVector(int n) {
    vector<int> vec(n);
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        vec[i] = rand() % 100;
    }
    return vec;
}

void shellSort1(vector<int>& a, int n) {
    int i, j, key;
    int gap = n / 2;
    while(1) {
        if (gap % 2 == 0) {
            gap++;
        }
        for (i = gap; i < n; i ++ ) {
            key = a[i];
            for (j = i; j >= gap && a[j - gap] > key; j -= gap) {
                a[j] = a[j - gap];
            }
            a[j] = key;
        }
        if (gap == 1)
            break;
        gap = gap / 2;
    }

}

void checkSort(vector<int>& a, int n) {
    int i;
    bool sorted = true;
    for (i = 0; i < n-1; i++) {
        if (a[i] > a[i + 1]) {
            sorted = false;
        }
        if (!sorted) {
            break;
        }
    }
    if (sorted) {
        cout << "정렬 완료.\n";
    }
    else {
        cout << "정렬 오류.\n";
    }
}

int main() {
    int n = 20000000;
    vector<int> vec = randomVector(n);
    //cout << "Random Vector: ";
    //for (int i = 0; i < n; i++) {
    //    cout << vec[i] << " ";
    //}
    auto start = chrono::high_resolution_clock::now();
    shellSort1(vec, n);
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end - start;
    //cout << "\nSorted Vector: ";
    //for (int i = 0; i < n; i++) {
    //    cout << vec[i] << " ";
    //}
    //cout << endl;
    checkSort(vec, n);
    cout << "Runtime: " << duration.count() << " seconds." << endl;
    return 0;
}

Gap Sequence 3*k + 1

#include <iostream>
#include <chrono>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

vector<int> randomVector(int n) {
    vector<int> vec(n);
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        vec[i] = rand() % 100;
    }
    return vec;
}

void shellSort2(vector<int>& a, int n) {
    int i, j, key;
    int gap= n;
    while (1) {
        gap = (gap / 3) + 1;
        for (i = gap; i < n; i++) {
            key = a[i];
            for (j = i; j >= gap && a[j - gap] > key; j -= gap) {
                a[j] = a[j - gap];
            }
            a[j] = key;
        }
        if (gap == 1)
            break;
    }
}

void checkSort(vector<int>& a, int n) {
    int i;
    bool sorted = true;
    for (i = 0; i < n-1; i++) {
        if (a[i] > a[i + 1]) {
            sorted = false;
        }
        if (!sorted) {
            break;
        }
    }
    if (sorted) {
        cout << "정렬 완료.\n";
    }
    else {
        cout << "정렬 오류.\n";
    }
}

int main() {
    int n = 20000000;
    vector<int> vec = randomVector(n);
    //cout << "Random Vector: ";
    //for (int i = 0; i < n; i++) {
    //    cout << vec[i] << " ";
    //}
    auto start = chrono::high_resolution_clock::now();
    shellSort2(vec, n);
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end - start;
    //cout << "\nSorted Vector: ";
    //for (int i = 0; i < n; i++) {
    //    cout << vec[i] << " ";
    //}
    //cout << endl;
    checkSort(vec, n);
    cout << "Runtime: " << duration.count() << " seconds." << endl;
    return 0;
}