1_selec_sort.cpp

#include<iostream>
#include<chrono>
#include<bits/stdc++.h>
using namespace std;
void selectionSort(vector<int>& arr , int n)
{
    for(int i=0 ; i<n-1 ; i++)  // n-1 number of passes
    {
        int min = i;  // let this be the index of the min element
        for(int j=i+1 ; j<n; j++)  // compare with all the succeeding elements of the array
        {
            if(arr[j]<arr[min])
            min = j;
        }
        swap(arr[min] , arr[i]);
    }
}
void input_generator(vector<pair<int,int>> &store)
{
    for(int i=10 ; i<=1e4 ; i+=1000)
    {
        vector<int> arr(i);
        generate(arr.begin() , arr.end() , rand) ;
    
        clock_t time_req;
        int t=0;
        for(int m=1 ; m<=10 ; m++)
        {
            time_req = clock();
            selectionSort(arr,i);
            time_req = clock() - time_req;
            t+=(time_req) ;
        }
        t=(t/10);
        store.push_back({t,i});

    }
}
int main()
{

    vector<pair<int,int>> store;
    input_generator(store);

    for(auto i : store)
    {
        cout << "Time " << "\t" << "Number of inputs " << endl;
        cout << i.first << "\t" << i.second << endl;
    }
    return 0;
}
// Description about the code
/*
    Analysing the time complexity of Selection Sort.
    1. Taking varied inputs in the array (generating the inputs using generate function:- generate(arr.begin(),arr.end(),rand)). 
    Made an input generator function which reapeated generates the asked number of inputs.
    2. Running Selection sort for the generated outputs for 10 times and taking average of that time.
    3.Plotting the graph between number of inputs and the time taken.
    
    As complexity of selection sort is of the order of n^2 we get a parabolic graph.
    (Graph plotted in desmos)
*/

// scale up and scale down of time
//CLOCKS_PER_SEC macro for converting the time generated by clock into seconds