algorithmic_complexity_cpp.cpp

# -*- coding: utf-8 -*-
"""Algorithmic_Complexity.cpp

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/1oFy60PSz1Jq5Uj8hwKcBbFD8LJ9p0K2e
"""

# Commented out IPython magic to ensure Python compatibility.
# %%writefile sorting_algorithms.cpp
# #include <iostream>
# #include <vector>
# #include <chrono> // To measure time taken by sorting algorithms
# 
# using namespace std;
# using namespace std::chrono;
# 
# // Function to perform Bubble Sort
# void bubbleSort(vector<int>& arr) {
#     int n = arr.size();
#     for (int i = 0; i < n - 1; i++) {
#         for (int j = 0; j < n - i - 1; j++) {
#             if (arr[j] > arr[j + 1]) {
#                 swap(arr[j], arr[j + 1]);
#             }
#         }
#     }
# }
# 
# // Function to merge two halves for Merge Sort
# void merge(vector<int>& arr, int left, int mid, int right) {
#     int n1 = mid - left + 1;
#     int n2 = right - mid;
# 
#     vector<int> L(n1), R(n2);
# 
#     for (int i = 0; i < n1; i++)
#         L[i] = arr[left + i];
#     for (int j = 0; j < n2; j++)
#         R[j] = arr[mid + 1 + j];
# 
#     int i = 0, j = 0, k = left;
#     while (i < n1 && j < n2) {
#         if (L[i] <= R[j]) {
#             arr[k] = L[i];
#             i++;
#         } else {
#             arr[k] = R[j];
#             j++;
#         }
#         k++;
#     }
# 
#     while (i < n1) {
#         arr[k] = L[i];
#         i++;
#         k++;
#     }
# 
#     while (j < n2) {
#         arr[k] = R[j];
#         j++;
#         k++;
#     }
# }
# 
# // Function to perform Merge Sort
# void mergeSort(vector<int>& arr, int left, int right) {
#     if (left >= right) return;
#     int mid = left + (right - left) / 2;
#     mergeSort(arr, left, mid);
#     mergeSort(arr, mid + 1, right);
#     merge(arr, left, mid, right);
# }
# 
# int main() {
#     int N;
#     cout << "Enter the number of delivery times: ";
#     cin >> N;
# 
#     vector<int> deliveryTimes(N);
#     cout << "Enter the delivery times (in minutes): ";
#     for (int i = 0; i < N; ++i) {
#         cin >> deliveryTimes[i];
#     }
# 
#     // Bubble Sort
#     vector<int> bubbleSortedTimes = deliveryTimes;
#     auto startBubble = high_resolution_clock::now();
#     bubbleSort(bubbleSortedTimes);
#     auto endBubble = high_resolution_clock::now();
#     auto durationBubble = duration_cast<microseconds>(endBubble - startBubble);
# 
#     // Merge Sort
#     vector<int> mergeSortedTimes = deliveryTimes;
#     auto startMerge = high_resolution_clock::now();
#     mergeSort(mergeSortedTimes, 0, N - 1);
#     auto endMerge = high_resolution_clock::now();
#     auto durationMerge = duration_cast<microseconds>(endMerge - startMerge);
# 
#     // Output Sorted Times and Durations
#     cout << "Sorted times using Bubble Sort: ";
#     for (int i = 0; i < N; ++i) {
#         cout << bubbleSortedTimes[i] << " ";
#     }
#     cout << "\nTime taken by Bubble Sort: " << durationBubble.count() << " microseconds\n";
# 
#     cout << "Sorted times using Merge Sort: ";
#     for (int i = 0; i < N; ++i) {
#         cout << mergeSortedTimes[i] << " ";
#     }
#     cout << "\nTime taken by Merge Sort: " << durationMerge.count() << " microseconds\n";
# 
#     // Time Complexity Explanation
#     cout << "\nTime Complexity:\n";
#     cout << "Bubble Sort: O(N^2) - Inefficient for large datasets\n";
#     cout << "Merge Sort: O(N log N) - More efficient, especially for larger datasets\n";
# 
#     return 0;
# }
#

!g++ sorting_algorithms.cpp -o sorting_algorithms

!./sorting_algorithms

"""#**Algorithmic Complexity Analysis**

**Bubble Sort**

> Bubble Sort works by repeatedly stepping through the list of delivery times, comparing adjacent elements, and swapping them if they’re in the wrong order. This process repeats for every element in the list, which means that for a list of N delivery times, the algorithm may need to perform up to N * (N - 1) / 2 comparisons and swaps in the worst case.


> This makes the time complexity of Bubble Sort O(N²), where N is the number of delivery times. This quadratic growth means that as the size of the input grows, the time it takes to sort the list increases dramatically. If the list doubles in size, the sorting time doesn’t just double — it quadruples. This is why Bubble Sort is considered inefficient for large datasets. It's simple and easy to implement but not a good choice when performance is important, especially for large numbers of deliveries.







**Merge Sort**


> On the other hand, Merge Sort is a more advanced algorithm that splits the list into halves, recursively sorts those halves, and then merges them back together in sorted order. It doesn’t need to compare each element with every other element like Bubble Sort. Instead, it repeatedly breaks the list down into smaller chunks, sorts them, and merges them efficiently.

> The time complexity of Merge Sort is O(N log N). This logarithmic factor comes from the process of dividing the list in half repeatedly, while the linear factor (N) comes from the merging process. As a result, Merge Sort is much faster than Bubble Sort, especially when dealing with larger datasets. For example, if you double the size of the input, Merge Sort will only need a little more than twice the number of operations. This efficiency makes it a better choice for large sets of delivery times.





**Conclusion**

> Bubble Sort is inefficient for larger datasets due to its quadratic time complexity, while Merge Sort is significantly more efficient with its O(N log N) time complexity. The real-world implication is that if you’re dealing with a small number of deliveries, either algorithm may suffice, but for larger numbers of deliveries, Merge Sort will perform far better and save both time and computational resources.


"""