Write a program that creates three identical arrays, list1, list2, and list3, of

Question

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

BASED ON THE ABOVE GUIDELINES HOW WOULD I MAKE THE FOLLOWING CODE WORK FOR SORTING 5000 ELEMENTS INSTEAD OF THE 10 SPECIFIED???

//Header file//

searchSortAlgorithms.h

void swap(int *xp, int *yp);

void bubbleSort(int arr[], int n);

void selectionSort(int arr[], int n);

void insertionSort(int arr[], int n);

void printArray(int arr[], int size);

//Main//

Ch18_Ex15.cpp

#include

#include

#include "searchSortAlgorithms.h"

using namespace std;

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

// A function to implement bubble sort

void bubbleSort(int arr[], int n)

{

int i, j, comparison = 0;

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

// Last i elements are already in place

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

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

comparison += 1;

swap(&arr[j], &arr[j+1]);

}

}

}

cout<<" Number of Comparison Made using Bubble Sort Algorithm is: "<

}

void selectionSort(int arr[], int n)

{

int i, j, min_idx, comparison = 0;

// One by one move boundary of unsorted subarray

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

{

// Find the minimum element in unsorted array

min_idx = i;

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

if (arr[j] < arr[min_idx]){

min_idx = j;

}

comparison += 1;

// Swap the found minimum element with the first element

swap(&arr[min_idx], &arr[i]);

}

}

cout<<" Number of Comparison Made using Selection Sort Algorithm is: "<

}

/* Function to sort an array using insertion sort*/

void insertionSort(int arr[], int n)

{

int i, key, j, comparison = 0;

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

{

key = arr[i];

j = i-1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j >= 0 && arr[j] > key)

{

arr[j+1] = arr[j];

j = j-1;

}

comparison += 1;

arr[j+1] = key;

}

cout<<" Number of Comparison Made using Insertion Sort Algorithm is: "<

}

/* Function to print an array */

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

cout<

cout<

}

// Driver program to test above functions

int main()

{

int list1[] = {64, 34, 25, 12, 22, 11, 90, 76, 90, 100};

int list2[] = {64, 34, 25, 12, 22, 11, 90, 76, 90, 100};

int list3[] = {64, 34, 25, 12, 22, 11, 90, 76, 90, 100};

int n = sizeof(list1)/sizeof(list1[0]);

bubbleSort(list1, n);

cout<< "Sorted array using Bubble Sort is: "<

printArray(list1, n);

selectionSort(list2, n);

cout<< "Sorted array using Selection Sort is: "<

printArray(list2, n);

insertionSort(list3, n);

cout<< "Sorted array using Insertion Sort is: "<

printArray(list3, n);   

return 0;

}

Sample output:

C:WINDOWS system32cmd.exe Number of Comparison Made using Bubble Sort Algorithm is: 15 orted array using Bubble Sort is: 12 25 34 64 76 90 90 100 Number of Comparison Made using Selection Sort Algorithm is: 45 orted array using Selection Sort is: 12 25 34 64 76 90 90 100 Number of Comparison Made using Insertion Sort Algorithm is: 9 orted array us ing Insertion Sort is 12 25 34 64 76 90 90 100 Press any key to continue .. .

Explanation / Answer

The code will be as follows :

#include <bits/stdc++.h>
using namespace std;
#include "searchSortAlgorithms.h"
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j, comparison = 0;
for (i = 0; i < n-1; i++){
// Last i elements are already in place
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]){
comparison += 1;
swap(&arr[j], &arr[j+1]);
}
}
}
cout<<" Number of Comparison Made using Bubble Sort Algorithm is: "<< comparison<<endl;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx, comparison = 0;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++){
if (arr[j] < arr[min_idx]){
min_idx = j;
}
comparison += 1;
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}
cout<<" Number of Comparison Made using Selection Sort Algorithm is: "<< comparison <<endl;
}
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j, comparison = 0;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
comparison += 1;
arr[j+1] = key;
}
cout<<" Number of Comparison Made using Insertion Sort Algorithm is: "<< comparison <<endl;
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout<< arr[i] << " " ;
cout << endl;
}
// Driver program to test above functions
int main()
{
int list1[5000];
int list2[5000];
int list3[5000];
for(int i = 0; i < 5000 ;i++)
{
list1[i] = rand() % 5000; // will generate random numbers between 0 and 5000
list2[i] = rand() % 5000;
list3[i] = rand() % 5000;
}
int n = sizeof(list1)/sizeof(list1[0]);
bubbleSort(list1, n);
cout<< "Sorted array using Bubble Sort is: "<< endl;
printArray(list1, n);
selectionSort(list2, n);
cout<< "Sorted array using Selection Sort is: "<< endl;
printArray(list2, n);
insertionSort(list3, n);
cout<< "Sorted array using Insertion Sort is: "<< endl;
printArray(list3, n);
return 0;
}

#Note that I have randomly generated the array of length of 5000

It is kind of messy to show you the output, so try on your own in your own compiler

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.