Question

c++

For your program, you will choose either the Selection Sort algorithm or the Insertion Sort algorithm and create a recursive implementation of that algorithm. Your program should:

1. Randomly generate an array of at least 20 values.
2. Display the contents of that (unsorted) array.
3. Use the recursive implementation of either Selection or Insertion Sort to sort the values.
4. Display the contents of the now sorted array, to demonstrate the success of the algorithm.

Answer 1

#include <iostream>

#include <cstdlib>

#include <time.h>

using namespace std;

void swap(int arr[], int i, int j)

{

  int temp = arr[i];

  arr[i] = arr[j];

  arr[j] = temp;

}

void selectionSort(int arr[], int index, int length)

{

int min = index;

  for (int i = index + 1; i < length; i++)

  {

    // if arr[i] element is less, then it is the new minimum

    if (arr[i] < arr[min])

      min = i;  // update index of min element

  }

  

  // swap the minimum element in subarray

  swap(arr, min, index);

  if (index + 1 < length) {

    selectionSort(arr, index + 1, length);

  }

}

int main() {

//Initiliaze the random seed

srand(time(NULL));

// Generate an array of 20 random numbers between 0 to 100

int arr[20];

// A for loop to populate the array

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

//generate the number between 0 and 100 and store it

arr[i] = rand() % 100 + 1;

}

// Display the unsorted array

cout<<"\nUnsorted Array :"<<endl;

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

//Display element

cout<<arr[i]<<" ";

}

//Call to the selection sort algorithm

selectionSort(arr, 0 , 20);

// Display the sorted array

cout<<"\nSorted Array :"<<endl;

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

//Display element

cout<<arr[i]<<" ";

}

}