Comparision with Quick Sort

 #include <iostream>
#include <vector>
#include <map>
#include <climits>
#include <chrono>  // Added for timing
using namespace std;
using namespace std::chrono;  // Added for chrono

#define MAP_SIZE USHRT_MAX
#define OFFSET MAP_SIZE/2

void Map_sort(vector<int> &nums) {
    vector<int> temp;
    int arr[MAP_SIZE] = {0};
    int maxElement = SHRT_MIN;
    int minElement = SHRT_MAX;
    
    for(int i=0; i<nums.size(); i++) {
        if(nums[i] > maxElement) maxElement = nums[i];
        if(nums[i] < minElement) minElement = nums[i];
        arr[nums[i]+OFFSET]++;
    }
    
    int j=0;
    for(int i=minElement; i<= maxElement; i++) {
        if(arr[i+OFFSET] >= 1) { 
            for(int count=0; count<arr[i+OFFSET]; count++) { 
                nums[j++] = i;
            }
        }
    }
}

int partition(vector<int>& nums, int low, int high) {
    int pivot = nums[high];
    int i = low - 1;
    
    for(int j = low; j < high; j++) {
        if(nums[j] < pivot) {
            i++;
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i+1], nums[high]);
    return i+1;
}

void quickSort(vector<int>& nums, int low, int high) {
    if(low < high) {
        int pi = partition(nums, low, high);
        quickSort(nums, low, pi-1);
        quickSort(nums, pi+1, high);
    }
}

int main() {
   // vector<int> nums{89, 77, 66, 55, 33, 44, 22, -11, 89};
    vector<int> nums;
  for(int i = 0; i < 9000; i++) {
    nums.push_back(rand() % 10000 - 5000);
}
    const int repetitions = 10000;  // To get measurable times
    
    // Time Map_sort
    auto start_map = high_resolution_clock::now();
   // for(int i = 0; i < repetitions; i++) {
        vector<int> map_sorted = nums;
        Map_sort(map_sorted);
  //  }
    auto end_map = high_resolution_clock::now();
    cout << "map sorted elements are:";
    for(auto x:map_sorted)
    {
       cout << x << " "; 
    }
    cout << endl;
    // Time QuickSort
    auto start_quick = high_resolution_clock::now();
   // for(int i = 0; i < repetitions; i++) {
        vector<int> quick_sorted = nums;
        quickSort(quick_sorted, 0, quick_sorted.size()-1);
  //  }
    auto end_quick = high_resolution_clock::now();
    cout << "Quick sorted elements are:";
    for(auto x:quick_sorted)
    {
       cout << x << " "; 
    }
    cout << endl;

    // Calculate durations
    auto map_duration = duration_cast<microseconds>(end_map - start_map);
    auto quick_duration = duration_cast<microseconds>(end_quick - start_quick);

    // Display results
    cout << "Map_sort average time:   " << map_duration.count() << " μs\n";
    cout << "QuickSort average time:  " << quick_duration.count() << " μs\n";

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

VECPP.c

#include <tape_t.h> #include <string_t.h> #include <tuple_t.h> #include <bool_t.h> /**** first design #include, #define VAR, #define FUNC() and #ifdef, #elif and #endif *****/ enum MacroType {     define_t,     include_t,     line_t,     undef_t,     error_tt,     pragma_t,     defined_t,     if_t,     ifdef_t,     ifndef_t,     elif_t,     else_t,     endif_t,     COMPILER_DATA,     UNDEFINED,     MAX_TYPE }; MacroType getIndexFromStr(string_t s) {     string_t tmp;     char* arr[13] = { "define","include","line","undef","error","pragma","defined","if","ifdef","ifndef","elif","else","endif" };     for(int i=0; i< 13; i++)     {         tmp = string(arr[i]);         if((compare(tmp,s)) == 0)         ...
Read more

Interview questions

Orion Innovations class A {           public:     A()     {         printf("A def ctor\n");     }     ~A()     {         printf("~A def dector\n");     }     char ac; }; static A statObject; int main() {     printf("Size of A = %d\n", sizeof(A));     printf("main()\n"); } //===================== //output: here // A def ctor Size of A = 1 main() ~A def dector struct A {     A() { cout << "A" << endl; }     ~A() { cout << "~A" << endl; } }; struct B {     B() { cout << "B" << endl; }     ~B() { cout << "~B" << endl; } }; struct D {     D( D& d ) { cout << "&D" << endl; }     D() { cout << "D" <...
Read more