Question

You are working as the software developer and need to identify the best sorting algorithm. Please refer to the following URL:

https://www.geeksforgeeks.org/sorting-algorithms/

You can pick any two-sorting algorithm. You need to determine which sorting algorithm is the best to sort the array of 10k elements.

Use the following steps to help with your solution:

1. Create C++ functions for any two-sorting algorithm.
2. Write down the random array generation function to generate at least 10k elements.
3. Pass the same array into both the sorting algorithm.
4. Calculate the end transactiontime-start transactiontime for each sorting algorithm.
5. Determine the best algorithm for sorting 10k elements based on the transaction time.

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

#include<iostream>

#include<stdlib.h>

#include<time.h>

#include <chrono>

#include <unistd.h>

using namespace std;

//method to sort an array of size n using selection sort algorithm

void selectionSort(int *data,int n) {

                                for (int i = 0; i < n - 1; i++) {

                                               // finding the index of smallest element in the unsorted array

                                               int index_min = i;

                                               for (int j = i + 1; j < n; j++)

                                                               if (data[j] < data[index_min])

                                                                               index_min = j;

                                               // swapping element at i with element at index_min

                                               int temp = data[index_min];

                                               data[index_min] = data[i];

                                               data[i] = temp;

                                }

                               

                               

}

//method using bubble sort algorithm to sort numbers in an array

void bubbleSort(int *data, int n){

               

                for(int i=0;i<n;i++){

                                for(int j=0;j<n-1;j++){

                                               if(data[j]>data[j+1]){

                                                               // swapping element at j with element at j+1

                                                               int temp = data[j];

                                                               data[j] = data[j+1];

                                                               data[j+1] = temp;

                                               }

                                }

                }

}

//method to fill random elements in an array.

//the range of values in array is between 0 and n

void generateArray(int data[], int n){

                for(int i=0;i<n;i++){

                                data[i]=rand()%n;

                }

}

//method to copy one array to another

void copyArray(int source[], int dest[], int n){

                for(int i=0;i<n;i++){

                                dest[i]=source[i];

                }

}

int main(){

                //seeding random number generator

                srand(time(NULL));

                //number of elements

                const int n=10000;

                //declaring two arrays

                int data1[n];

                int data2[n];

                //filling random values in data1

                generateArray(data1,n);

                //copying data1 to data2, so that both arrays will be the same

                copyArray(data1,data2,n);

                //testing bubble sort

                cout<<"Testing bubble sort technique"<<endl;

                auto start = chrono::steady_clock::now(); //recording start time

                bubbleSort(data1,n); //bubble sorting data1

                auto end = chrono::steady_clock::now(); //recording end time

                //finding time taken in milli seconds and displaying it

                auto time1=chrono::duration_cast<chrono::milliseconds>(end - start).count();

                cout<<time1<<" milliseconds to sort an array with "<<n<<" elements"<<endl;

                //doing the same for selection sort

                cout<<"Testing selection sort technique"<<endl;

                start = chrono::steady_clock::now();

                selectionSort(data2,n);

                end = chrono::steady_clock::now();

                auto time2=chrono::duration_cast<chrono::milliseconds>(end - start).count();

                cout<<time2<<" milliseconds to sort an array with "<<n<<" elements"<<endl;

               

                //comparing two times and displaying which algorithm is more efficient

                if(time1<time2){

                                cout<<"Bubble sort is more efficient"<<endl;

                }else{

                                cout<<"Selection sort is more efficient"<<endl;

                }

               

                return 0;

}

/*OUTPUT*/

Testing bubble sort technique

1067 milliseconds to sort an array with 10000 elements

Testing selection sort technique

270 milliseconds to sort an array with 10000 elements

Selection sort is more efficient