using uint64_t from cstdint header

and doxygen formatiing
rakshitraj · Nov 29, 2020 · 047578b · 047578b
1 parent 81560e8
commit 047578b
Showing 1 changed file with 30 additions and 29 deletions.
diff --git a/sorting/count_inversions.cpp b/sorting/count_inversions.cpp
@@ -10,11 +10,11 @@
  * The count of inversions help to determine how close the array
  * is to being sorted in ASCENDING order.
  *
- * two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
+ * two elements a[i] and a[j] form an inversion if `a[i]` > `a[j]` and i < j
  *
- * Time Complexity --> O(n.log n)
+ * Time Complexity --> `O(n.log n)`
 
- * Space Complexity --> O(n) ; additional array temp[1..n]
+ * Space Complexity --> `O(n)` ; additional array `temp[1..n]`
  * ### Algorithm
 
  *   1. The idea is similar to merge sort, divide the array into two equal or
@@ -43,6 +43,7 @@
 #include <cassert>
 #include <iostream>
 #include <vector>
+#include <cstdint>
 
 /**
  * @namespace sorting
@@ -71,18 +72,18 @@ namespace inversion {
  *
  * @param arr    input array, data-menber of vector
  * @param temp   stores the resultant merged array
- * @param left   lower bound of arr[] and left-sub-array
+ * @param left   lower bound of `arr[]` and left-sub-array
  * @param mid    midpoint, upper bound of left sub-array,
- *               (mid+1) gives the lower bound of right-sub-array
- * @param right  upper bound of arr[] and right-sub-array
+ *               `(mid+1)` gives the lower bound of right-sub-array
+ * @param right  upper bound of `arr[]` and right-sub-array
  * @returns number of inversions found in merge step
  */
 template <typename T>
-int merge(T* arr, T* temp, int left, int mid, int right) {
-    int i = left;       /* i --> index of left sub-array */
-    int j = mid + 1;    /* j --> index for right sub-array */
-    int k = left;       /* k --> index for resultant array temp */
-    int inv_count = 0;  // inversion count
+uint64_t merge(T* arr, T* temp, uint64_t left, uint64_t mid, uint64_t right) {
+    uint64_t i = left;       /* i --> index of left sub-array */
+    uint64_t j = mid + 1;    /* j --> index for right sub-array */
+    uint64_t k = left;       /* k --> index for resultant array temp */
+    uint64_t inv_count = 0;  // inversion count
 
     while ((i <= mid) && (j <= right)) {
         if (arr[i] <= arr[j]) {
@@ -123,8 +124,8 @@ int merge(T* arr, T* temp, int left, int mid, int right) {
  * @returns number of inversions in array
  */
 template <typename T>
-int mergeSort(T* arr, T* temp, int left, int right) {
-    int mid = 0, inv_count = 0;
+uint64_t mergeSort(T* arr, T* temp, uint64_t left, uint64_t right) {
+    uint64_t mid = 0, inv_count = 0;
     if (right > left) {
         // midpoint to split the array
         mid = (right + left) / 2;
@@ -154,7 +155,7 @@ int mergeSort(T* arr, T* temp, int left, int right) {
  * @returns number of inversions in input array, sorts the array
  */
 template <class T>
-int countInversion(T* arr, const int size) {
+int countInversion(T* arr, const uint64_t size) {
     std::vector<T> temp;
     temp.reserve(size);
     temp.assign(size, 0);
@@ -169,9 +170,9 @@ int countInversion(T* arr, const int size) {
  *
  */
 template <typename T>
-void show(T* arr, const int array_size) {
+void show(T* arr, const uint64_t array_size) {
     std::cout << "Printing array: \n";
-    for (int i = 0; i < array_size; i++) {
+    for (uint64_t i = 0; i < array_size; i++) {
         std::cout << " " << arr[i];
     }
     std::cout << "\n";
@@ -186,35 +187,35 @@ void show(T* arr, const int array_size) {
  */
 static void test() {
     // Test 1
-    std::vector<int> arr1 = {
+    std::vector<uint64_t> arr1 = {
         100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84,
         83,  82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67,
         66,  65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50,
         49,  48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33,
         32,  31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16,
         15,  14, 13, 12, 11, 10, 9,  8,  7,  6,  5,  4,  3,  2,  1};
-    int size1 = arr1.size();
-    int inv_count1 = 4950;
-    int result1 = sorting::inversion::countInversion(arr1.data(), size1);
+    uint64_t size1 = arr1.size();
+    uint64_t inv_count1 = 4950;
+    uint64_t result1 = sorting::inversion::countInversion(arr1.data(), size1);
     assert(inv_count1 == result1);
     // Test 2
     std::vector<int> arr2 = {22, 66, 75, 23, 11, 87, 2, 44, 98, 43};
-    int size2 = arr2.size();
-    int inv_count2 = 20;
-    int result2 = sorting::inversion::countInversion(arr2.data(), size2);
+    uint64_t size2 = arr2.size();
+    uint64_t inv_count2 = 20;
+    uint64_t result2 = sorting::inversion::countInversion(arr2.data(), size2);
     assert(inv_count2 == result2);
     // Test 3
     std::vector<double> arr3 = {33.1, 45.2, 65.4, 76.5, 1.0,
                                 2.9,  5.4,  7.7,  88.9, 12.4};
-    int size3 = arr3.size();
-    int inv_count3 = 21;
-    int result3 = sorting::inversion::countInversion(arr3.data(), size3);
+    uint64_t size3 = arr3.size();
+    uint64_t inv_count3 = 21;
+    uint64_t result3 = sorting::inversion::countInversion(arr3.data(), size3);
     assert(inv_count3 == result3);
     // Test 4
     std::vector<char> arr4 = {'a', 'b', 'c', 'd', 'e'};
-    int size4 = arr4.size();
-    int inv_count4 = 0;
-    int result4 = sorting::inversion::countInversion(arr4.data(), size4);
+    uint64_t size4 = arr4.size();
+    uint64_t inv_count4 = 0;
+    uint64_t result4 = sorting::inversion::countInversion(arr4.data(), size4);
     assert(inv_count4 == result4);
 }