Created
December 9, 2025 16:56
-
-
Save Madman10K/695e7e57c05c3f619306c56ddb2bbeb0 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <chrono> | |
| #include <iostream> | |
| #include <random> | |
| #include <vector> | |
| void bubble_sort(std::vector<int64_t>& a) noexcept | |
| { | |
| const size_t n = a.size(); | |
| if (n < 2) | |
| return; | |
| bool swapped = false; | |
| for (size_t i = 0; i < n - 1; ++i) | |
| { | |
| swapped = false; | |
| for (size_t j = 0; j < n - 1 - i; ++j) | |
| { | |
| if (a[j] > a[j + 1]) | |
| { | |
| std::swap(a[j], a[j + 1]); | |
| swapped = true; | |
| } | |
| } | |
| if (!swapped) | |
| break; | |
| } | |
| } | |
| void merge_sort_rec(std::vector<int64_t>& a, std::vector<int64_t>& temp, const size_t left, const size_t right) noexcept | |
| { | |
| if (right - left <= 1) | |
| return; | |
| const size_t mid = left + (right - left) / 2; | |
| merge_sort_rec(a, temp, left, mid); | |
| merge_sort_rec(a, temp, mid, right); | |
| size_t i = left; | |
| size_t j = mid; | |
| size_t k = left; | |
| while (i < mid && j < right) | |
| { | |
| if (a[i] <= a[j]) | |
| temp[k++] = a[i++]; | |
| else | |
| temp[k++] = a[j++]; | |
| } | |
| while (i < mid) | |
| temp[k++] = a[i++]; | |
| while (j < right) | |
| temp[k++] = a[j++]; | |
| for (size_t idx = left; idx < right; ++idx) | |
| a[idx] = temp[idx]; | |
| } | |
| void merge_sort(std::vector<int64_t>& a) noexcept | |
| { | |
| if (a.size() < 2) | |
| return; | |
| std::vector<int64_t> temp(a.size()); | |
| merge_sort_rec(a, temp, 0, a.size()); | |
| } | |
| void quick_sort_rec(std::vector<int64_t>& a, const size_t left, const size_t right) noexcept | |
| { | |
| if (right <= left + 1) | |
| return; | |
| size_t i = left; | |
| size_t j = right - 1; | |
| const int64_t pivot = a[left + (right - left) / 2]; | |
| while (i <= j) | |
| { | |
| while (a[i] < pivot) | |
| ++i; | |
| while (a[j] > pivot) | |
| --j; | |
| if (i <= j) | |
| { | |
| std::swap(a[i], a[j]); | |
| ++i; | |
| if (j == 0) | |
| break; | |
| --j; | |
| } | |
| } | |
| if (left < j + 1) | |
| quick_sort_rec(a, left, j + 1); | |
| if (i < right) | |
| quick_sort_rec(a, i, right); | |
| } | |
| void quick_sort(std::vector<int64_t>& a) noexcept | |
| { | |
| if (!a.empty()) | |
| quick_sort_rec(a, 0, a.size()); | |
| } | |
| template <typename Func> | |
| int64_t time_sort(Func sort_func, const std::vector<int64_t>& data) | |
| { | |
| std::vector<int64_t> copy = data; // ensure same input for each algorithm | |
| const auto start = std::chrono::high_resolution_clock::now(); | |
| sort_func(copy); | |
| const auto end = std::chrono::high_resolution_clock::now(); | |
| return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count(); | |
| } | |
| #define MIN_N 1000 | |
| #define MAX_N 20000 | |
| #define STEP_N 1500 | |
| #define TRIALS 10 | |
| int main() | |
| { | |
| std::mt19937 rng(std::random_device{}()); | |
| std::uniform_int_distribution<int64_t> dist(0, 1'000'000); | |
| // CSV header | |
| std::cout << "n,bubble_us,merge_us,quick_us" << std::endl; | |
| for (size_t n = MIN_N; n <= MAX_N; n += STEP_N) | |
| { | |
| int64_t bubble_total = 0; | |
| int64_t merge_total = 0; | |
| int64_t quick_total = 0; | |
| for (int64_t t = 0; t < TRIALS; ++t) | |
| { | |
| std::vector<int64_t> data(n); | |
| for (size_t i = 0; i < n; ++i) | |
| data[i] = dist(rng); | |
| bubble_total += time_sort(bubble_sort, data); | |
| merge_total += time_sort(merge_sort, data); | |
| quick_total += time_sort(quick_sort, data); | |
| } | |
| const int64_t bubble_avg = bubble_total / TRIALS; | |
| const int64_t merge_avg = merge_total / TRIALS; | |
| const int64_t quick_avg = quick_total / TRIALS; | |
| std::cout << n << "," << bubble_avg << "," << merge_avg << "," << quick_avg << std::endl; | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment