Bubble Sort

#include <iostream>
#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; // Generating random integers between 0 to 99
    }
    return vec;
}

void bubbleSort(vector<int> &arr,int n) {
    int i, j, temp;

    for (i = n - 1; i > 0; i--) {
        for (j = 0; j < i; j++) {
            if (arr[j] < arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main() {
    int n = 6000; // Length of vector
    int start, end;
    vector<int> vec = randomVector(n);
    cout << "Random Vector: ";
    for (int i = 0; i < n; i++) {
        cout << vec[i] << " "; // Printing the generated vector
    }
    start = clock();
    bubbleSort(vec,n);
    end = clock();
    cout << "\nSorted Vector: ";
    for (int i = 0; i < n; i++) {
        cout << vec[i] << " "; // Printing the sorted vector
    }
    cout << endl;
    cout << n << ": " << end - start << endl;
    return 0;
}

N=10으로 하여 버블 정렬이 잘 작동되는지 확인해보았습니다.

N을 작게 했을 때는 시간이 제대로 측정되지 않아 N을 크게 하였습니다.
N= 1000에서 2000으로 증가했을 때 N이 2배가 됐으므로, N^2 증가가 확인되야 합니다.
즉, 4배가 되야 합니다.
time 이 10 에서 36으로 약 4배로 된 것을 확인할 수 있습니다.
또한 1000에서 4000으로 증가했을 때, N이 4배가 됐으므로 N^2 증가는 16배가 되어야 합니다.
time 이 10에서 184 로, 약 16배로 증가한 것을 확인할 수 있습니다.
위와 같이 N=5000, 6000 에서도 각각 약 N^2 값인 25배, 36배로 증가 된 것을 확인할 수 있습니다.