Question

I actually would like you to take a look at my code and point it out if there is anything wrong with it. I think there might be because there are some values that are the same in different arrays.

QUESTION: C++ 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.

CODE:

#include<iostream>
#include<time.h>
#include<stdlib.h>

using namespace std;

int insertioncompare = 0;
int insertionexchange = 0;

int bubblecompare = 0;
int bubbleexchange = 0;

int selectioncompare = 0;
int selectionexchange = 0;

int shellcompare = 0;
int shellexchange = 0;

//insertion sort
void insertionSort(int size, int A[])
{
int temp;
int cmp = 0;
int x, y;
for (int x = 1; x < size; x++)
{
temp = A[x];
y = x - 1;
insertioncompare++;
while (y >= 0 && A[y] > temp)
{
insertioncompare++;
insertionexchange++;
A[y + 1] = A[y];
y = y - 1;
}
A[y + 1] = temp;
}
}

//bubble sort
void bubbleSort(int size, int A[])
{
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
bubblecompare++;
if (A[i] > A[j])
{
bubbleexchange++;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
}

//selection sort
void selectionSort(int size, int A[])
{
int min;
for (int i = 0; i < size - 1; i++)
{
min = i;
for (int j = i + 1; j < size; j++)
{
selectioncompare++;
if (A[j] < A[min])
min = j;
}
selectionexchange++;
int temp = A[min];
A[min] = A[i];
A[i] = temp;
}
}

//Shell Sort
void shellSort(int size, int A[])
{

for (int space = size / 2; space > 0; space /= 2)
{
for (int i = space; i < size; i += 1)
{
int temp = A[i];
int j;
shellcompare++;
for (j = i; j >= space && A[j - space] > temp; j -= space)
{
shellcompare++;
shellexchange++;
A[j] = A[j - space];
}
A[j] = temp;
}
}
}

int main()
{
int Isort[1000];
int Bsort[1000];
int Ssort[1000];
int ShellSort[1000];
//creating random array
for (int i = 0; i < 1000; ++i)
{
Isort[i] = rand();
}
//creating random arry for bubble sort
for (int j = 0; j < 1000; ++j)
{
Bsort[j] = Isort[j];
}
//creating random array for selection sort
for (int j = 0; j < 1000; ++j)
{
Ssort[j] = Isort[j];
}
//creating random aray for shell sort
for (int j = 0; j < 1000; ++j)
{
ShellSort[j] = Isort[j];
}

insertionSort(1000, Isort);
bubbleSort(1000, Bsort);
selectionSort(1000, Ssort);
shellSort(1000, ShellSort);
  
cout << "Array 1:";
cout << "\nInsertion sort: \nCompare = " << insertioncompare << " Exchange = " << insertionexchange;
cout << "\nBubble sort: \nCompare = " << bubblecompare << " Exchange = " << bubbleexchange;
cout << "\nSelection sort: \nCompare = " << selectioncompare << " Exchange = " << selectionexchange;
cout << "\nShell sort: \nCompare = " << shellcompare << " Exchange = " << shellexchange;
cout << endl << endl;

insertionSort(1000, Isort);
bubbleSort(1000, Bsort);
selectionSort(1000, Ssort);
shellSort(1000, ShellSort);

cout << "Array 2:";
cout << "\nInsertion sort: \nCompare = " << insertioncompare << " Exchange = " << insertionexchange;
cout << "\nBubble sort: \nCompare = " << bubblecompare << " Exchange = " << bubbleexchange;
cout << "\nSelection sort: \nCompare = " << selectioncompare << " Exchange = " << selectionexchange;
cout << "\nShell sort: \nCompare = " << shellcompare << " Exchange = " << shellexchange;
cout << endl << endl;

insertionSort(1000, Isort);
bubbleSort(1000, Bsort);
selectionSort(1000, Ssort);
shellSort(1000, ShellSort);

cout << "Array 3:";
cout << "\nInsertion sort: \nCompare = " << insertioncompare << " Exchange = " << insertionexchange;
cout << "\nBubble sort: \nCompare = " << bubblecompare << " Exchange = " << bubbleexchange;
cout << "\nSelection sort: \nCompare = " << selectioncompare << " Exchange = " << selectionexchange;
cout << "\nShell sort: \nCompare = " << shellcompare << " Exchange = " << shellexchange;
cout << endl;
}

OUTPUT:

Array 1:
Insertion sort:
Compare = 249144 Exchange = 248145
Bubble sort:
Compare = 499500 Exchange = 246686
Selection sort:
Compare = 499500 Exchange = 999
Shell sort:
Compare = 16332 Exchange = 8326

Array 2:
Insertion sort:
Compare = 250143 Exchange = 248145
Bubble sort:
Compare = 999000 Exchange = 246686
Selection sort:
Compare = 999000 Exchange = 1998
Shell sort:
Compare = 24338 Exchange = 8326

Array 3:
Insertion sort:
Compare = 251142 Exchange = 248145
Bubble sort:
Compare = 1498500 Exchange = 246686
Selection sort:
Compare = 1498500 Exchange = 2997
Shell sort:
Compare = 32344 Exchange = 8326

Answer 1

The values are same because the random function you are using is infact not really random. When you use rand function like you are not really getting random values. If you print these values then you will see the sequence generated each time is same. So what we do is we seed the rand function with initial value which should be different each time so that a set of random values is generated each time. Now since seed should also be random then we use a time function for this. So before using the rand function we seed the rand function. So the program will look something like this:

   srand(time(0)); // Seeding the initial value for rand function.

// Creating random array.
   for (int i = 0; i < 1000; ++i) {
       Isort[i] = rand();
   }

Hope this helps. If you have any queries or suggestions regarding the answers please leave them in the comments section so I can update and improve the answer. Thank you.