Question

c++ programming question: Use the random number generator in class Random to store a list of...

c++

  • programming question: Use the random number generator in class Random to store a list of 1000 random integer values in an array.  
  • Create 3 arrays using this method.
  • Apply each of the insertion, bubble, selection and shell sort algorithms to each array.
  • Determine the number of comparisons and exchanges for each sort algorithm for each array.
  • create table to print out the results.
first array second array third array
comparisons exchanges comparisons exchanges comparisons exchanges
insertion
bubble
selection
shell

Homework Answers

Answer #1

Here is the solution to above problem in C++. Please read the code comments for more information

C++ CODE

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

//bubble sort algorithm
void bubbleSort(int a[],int &cmp,int &swaps)
{
  
   for(int i=0;i<1000;++i)
   {
       for(int j=0;j<1000-i-1;++j)
       {
           cmp++;
           if(a[j]<a[j+1])
           {
               swaps++;
              
               int temp=a[j];
               a[j]=a[j+1];
               a[j+1]=temp;
           }
       }
   }
}

//insertion sort
void insertionSort(int a[], int &cmp,int &swaps)
{
int temp;
   int j;
for (int i = 1; i < 1000; i++)
{
temp = a[i];
j = i - 1;
  
while (j >= 0 && a[j] > temp)
{
   cmp++; //comparsions plus by 2
a[j + 1] = a[j];
swaps++;
j = j - 1;
}
//only one swap
a[j + 1] = temp;
}
}

//selection sort
void selectionSort(int a[], int &cmp,int &swaps)
{
int temp;

for (int i = 0; i <999; i++)
{
       temp = i;
for (int j = i+1; j < 1000; j++)
{
cmp++;
if (a[j] < a[temp])
temp = j;
       }
    int temp2 = a[temp];
    a[temp]=a[i];
    a[i]=temp2;
swaps++;
}
}
  

int main()
{
   srand(time(0));
   //thre array
   int a1[1000];
   int a2[1000];
   int a3[1000];
   //initialize the array
   for(int i=0;i<1000;++i)
   {
       a1[i]=rand()%1000;
       a2[i]=rand()%1000;
       a3[i]=rand()%1000;
      
   }
  
   cout<<"       FIRST ARRAY        SECOND ARRAY        THIRD ARRAY\n";
   cout<<"       CMP   EXH       CMP   EXH       CMP   EXH\n";
   cout<<"Insertion ";
   cout<<"   ";
   int cmp=0;
   int swaps=0;
   insertionSort(a1,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   insertionSort(a2,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   insertionSort(a3,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   cout<<endl;
   cout<<"Selection ";
   cout<<"   ";
   selectionSort(a1,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   selectionSort(a2,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   selectionSort(a3,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   cout<<endl;
   cout<<"Bubble   ";
   cout<<"   ";
   bubbleSort(a1,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   bubbleSort(a2,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   bubbleSort(a3,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
  
}

SCREENSHOT OF OUTPUT

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Using C++, Python, or Java, write a program that: In this programming exercise you will perform...
Using C++, Python, or Java, write a program that: In this programming exercise you will perform an empirical analysis of the QuickSort algorithm to study the actual average case behavior and compare it to the mathematically predicted behavior. That is, you will write a program that counts the number of comparisons performed by QuickSort on an array of a given size. You will run the program on a large number of arrays of a certain size and determine the average...
Please answer in C++ with the correct files (in bold). Thanks! Write a program that creates...
Please answer in C++ with the correct files (in bold). Thanks! Write a program that creates three identical arrays, list1, list2, and list3, of 5000 elements. The program then sorts list1 using bubble sort, list2 using selection sort, and list3 using insertion sort and outputs the number of comparisons and item assignments made by each sorting algorithm. Please use the file names listed below since your file will have the following components: Ch18_Ex15.cpp searchSortAlgorithms.h
In C programming Propose an algorithm to generate random numbers and store each value as an...
In C programming Propose an algorithm to generate random numbers and store each value as an entry in an array.
Exercise 4–Timing Sorting AlgorithmCollect the run times for either selection sort or insertion sort (use random...
Exercise 4–Timing Sorting AlgorithmCollect the run times for either selection sort or insertion sort (use random values for an array and sorted values; sorted the same list twice and collect time each time) for the following array sizes: 1000, 2000, and 10000. You should be able to confirm that the runtime is n^2 for unsorted list (i.e., going from 1000 to 2000 should be about 4 times slower and going from 1000 to 10000 should be about 100times slower).
Part 1 - LIST Create an unsorted LIST class ( You should already have this code...
Part 1 - LIST Create an unsorted LIST class ( You should already have this code from a prior assignment ). Each list should be able to store 100 names. Part 2 - Create a Class ArrayListClass It will contain an array of 27 "list" classes. Next, create a Class in which is composed a array of 27 list classes. Ignore index 0... Indexes 1...26 correspond to the first letter of a Last name. Again - ignore index 0. index...
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
For this lab assignment you will need to write some code and create some graphs. You...
For this lab assignment you will need to write some code and create some graphs. You may use excel to create your graphs, or other language of your choice. Your data needs to demonstrate the experimental running time for Selection Sort (code in book), Merge Sort (code in book), and the Arrays.sort() method. Here is a basic outline of how you need to code this assignment. 1) Create several arrays of size 100, 1000, 10000, 100000, 1000000, … (you need...
Assignment #4 – Student Ranking : In this assignment you are going to write a program...
Assignment #4 – Student Ranking : In this assignment you are going to write a program that ask user number of students in a class and their names. Number of students are limited to 100 maximum. Then, it will ask for 3 test scores of each student. The program will calculate the average of test scores for each student and display with their names. Then, it will sort the averages in descending order and display the sorted list with students’...
Implementing Polynomials using Singly Linked List in C++ The Term Class Create a class to represent...
Implementing Polynomials using Singly Linked List in C++ The Term Class Create a class to represent a term in an algebraic expression. As defined here, a term consists of an integer coefficient and a nonnegative integer exponent. E.g. • in the term 4X2, the coefficient is 4 and the exponent 2 • in -6X8, the coefficient is -6 and the exponent 8 Your class will have a constructor that creates a Term object with a coefficient and exponent passed as...
Finish the code wherever it says TODO /**    * Node type for this list. Each...
Finish the code wherever it says TODO /**    * Node type for this list. Each node holds a maximum of nodeSize elements in an    * array. Empty slots are null.    */    private class Node {        /**        * Array of actual data elements.        */        // Unchecked warning unavoidable.        public E[] data = (E[]) new Comparable[nodeSize];        /**        * Link to next node.       ...