Question

PROVIDE CODE ONLY IN C++ / NO OTHER LANGUAGES

PLEASE ADD SELECTION SORT/ INSERTION SORT/ AND BUBBLE SORT FUNCTION TO THIS PROGRAM

#include <iostream>
#include<vector>
#include <algorithm >  
#include <chrono>   
#include <ctime>

using namespace std;

void bubblesSort()
{
// Please create Bubble Sort function// Make another for Selection Sort and  Insertion Sort
}

int main()
{
// empty vector
vector<int> data; // data [0], data [1]... data[N-1] <-- end(data)

// set of values to test N
for (auto N : { 20, 40, 50, 100, 120, 130, 140, 150, 200, 300, 5000, 7000 })
{
N = N * 100;
data.clear(); // wipe-out vector
data.resize(N); // resize

// anomyous/lambda function used to Generate PRN
auto random = [&N]() { return rand() % N; };

// Fill up the vector
generate(begin(data), end(data), random);

using namespace std::chrono;

// start time
auto time1 = high_resolution_clock::now();

// Call your function: bubble Sort
//sort(begin(data), end(data));

bubblesSort (data, N);

selectionSort();

insertionSort();

// end time
auto time2 = high_resolution_clock::now();

auto timeMeasure = duration_cast<milliseconds>(time2 - time1);

//
cout << "Time to sort : " << N << " number was: " << timeMeasure.count() << " milli-sec\n";

}

return 0;
}

Answer 1

#include <iostream>
#include<vector>
#include <algorithm>// no space here   
#include <chrono>   
#include <ctime>

using namespace std;

void swap(vector<int> &data, int i, int j)
{
    int tmp= data[i];
    data[i]=data[j];
    data[j]=data[i];
}



void bubblesSort( vector<int>&data)
{

   int n=data.size();  // will give us size of vector, you can also use N originally
        
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-i-1;j++){
                if(data[j]>data[j+1])
                swap(data,i,i+1);
            }
        }
        
}

void selectionSort(vector<int> &data){
    
    int n=data.size();
    
    
    for (int i = 0; i < n - 1; i++)
        {
                int min = i;
                for (int j = i + 1; j < n; j++)
                {
                        if (data[j] < data[min])
                                min = j;        // update index of min element
                }
                swap(data, min, i);
        }
    
}


void insertionSort(vector<int> &data){
    // Start from second element (element at index 0
        // is already sorted)
        int n=data.size();
        for (int i = 1; i < n; i++)
        {
                int value = data[i];
                int j = i;
                // Find the index j within the sorted subset arr[0..i-1]
                // where element arr[i] belongs
                while (j > 0 && data[j - 1] > value)
                {
                        data[j] = data[j - 1];
                        j--;
                }

                // Note that subarray arr[j..i-1] is shifted to
                // the right by one position i.e. arr[j+1..i]

                data[j] = value;
        }
}

int main()
{
// empty vector
vector<int> data; // data [0], data [1]... data[N-1] <-- end(data)

// set of values to test N
for (auto N : { 20, 40, 50, 100, 120, 130, 140, 150, 200, 300, 5000, 7000 })
{
N = N * 100;
data.clear(); // wipe-out vector
data.resize(N); // resize

// anomyous/lambda function used to Generate PRN
auto random = [&N]() { return rand() % N; };

// Fill up the vector
generate(data.begin(),data.end(), random);

using namespace std::chrono;

// start time
auto time1 = high_resolution_clock::now();

// Call your function: bubble Sort
//sort(begin(data), end(data));

bubblesSort (data); // i did not take N here

selectionSort(data);

insertionSort(data);

// end time
auto time2 = high_resolution_clock::now();

auto timeMeasure = duration_cast<milliseconds>(time2 - time1);

//
cout << "Time to sort : " << N << " number was: " << timeMeasure.count() << " milli-sec\n";

if(N==10000)
break;  // do not forget to break at some point or it will become a countless loop

}

return 0;
}