Implement (or use your code from previous practice and/or labs) selection, bubbl

Question

Implement (or use your code from previous practice and/or labs) selection, bubble, and insertion sort. For each algorithm, count the number of times it loops (you can make the sort methods return an integer with this count). Call each sorting algorithms on the following types of arrays:

an array of 10 integers already sorted into ascending order an array of 10 integers in the opposite order
an array of 10 random integers between 0 and 99
an array of 100 integers already sorted into ascending order an array of 100 integers in the opposite order

an array of 100 random integers between 0 and 99

Create a table of the number of times each algorithm looped for each type of array, save the table in a PDF document, and upload that document to Pilot along with your code.

Explanation / Answer

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

// insetion sort begins here
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
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;
}
arr[j+1] = key;
}
}

// A utility function ot print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf(" ");
}

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;
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])
swap(&arr[j], &arr[j+1]);
}

void selectionSort(int my_numbers[], int MAX)
{
int position, swap;
int i, j;

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

for (j = i + 1; j < MAX; j++)
{
if (my_numbers[position] > my_numbers[j])
position = j;
}
if (position != i)
{
swap = my_numbers[i];
my_numbers[i] = my_numbers[position];
my_numbers[position] = swap;
}
}

/*
cout<<" Sorted list is: ";
for (i = 0; i < MAX; i++)
cout<<" "<<my_numbers[i];
cout << endl;
*/
}

int main()
{
int count = 0;
  
while(count<6)
{
int arr1[100], arr2[100], arr3[100];
// ascending order 10 digits
int j=2;
if(count==0)
{
for(int i = 0; i<10; i++)
{
arr1[i] = i*j+11;
arr2[i] = i*j+11;
arr3[i] = i*j+11;
}
}
  
// descending order 10 digits
else if(count==1)
{
int j = 101;
for(int i = 0; i<10; i++)
{
arr1[i] = j-i*2;
arr2[i] = j-i*2;
arr3[i] = j-i*2;
}
}
  
// random 10 integers between 0-99
else if(count==2)
{
int i = 0;
//int arr1[100], arr2[100], arr3[100];
srand( (unsigned int) time(NULL) );
while(i<100)
{
arr1[i] =rand()%10 ;
arr2[i] = rand()%10;
arr3[i] = rand()%10;
}
}
  
// ascending order 100 integers
else if(count==3)
{
//int arr1[100], arr2[100], arr3[100];
int j = 0;
for(int i =25 ;i<125; i++)
{
arr1[j] = i;
arr2[j] = i;
arr3[j] = i;
j++;
}   
}
  
// descending order 100 integers
else if(count==4)
{
int j = 0;
//int arr1[100], arr2[100], arr3[100];
for(int i =125 ;i>25; i--)
{
arr1[j] = i;
arr2[j] = i;
arr3[j] = i;
j++;
}   
}
  
// random 100 integers between 0-99
else if(count==5)
{
int i = 0;
//int arr1[100], arr2[100], arr3[100];
srand( (unsigned int) time(NULL) );
while(i<100)
{
arr1[i] =rand()%100 ;
arr2[i] = rand()%100;
arr3[i] = rand()%100;
}
}

int n = sizeof(arr1)/sizeof(arr1[0]);
printf("Original Array is: ");
printArray(arr1, n);
bubbleSort(arr1, n);
printf("Bubble Sorted Array is: ");
printArray(arr1, n);

printf("Original Array is: ");
printArray(arr2, n);
insertionSort(arr2, n);
printf("Insertion Sorted Array is: ");
printArray(arr2, n);
  
  
printf("Original Array is: ");
printArray(arr3, n);
selectionSort(arr3, n);
printf("Insertion Sorted Array is: ");
printArray(arr3, n);
count++;
}
return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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