This program will compare two sorting methods, selection sort and the bubble sor

Question

This program will compare two sorting methods, selection sort and the bubble sort. The assignment is to generate a 1000 character array using a random generation method. Copy the random character array into another character array so that the sorting algorithms can be compared against the same array. (you should have two identical randomly generated character arrays.) Sort the first array using the selection sort method, counting the number of swaps (data exchanges) and comparisons used during the sorting process. Sort the second array using the bubble sort method, again counting the number of swaps and comparisons. The printed output should include the originally generated unsorted array, followed by each sorted array, swap count, and comparison count. The arrays should be labeled and printed nicely, with spaces between each element and a reasonable number of elements on each line. Experiment with changing the size of the arrays. You might want to use a constant for MAX_SIZE so that changing the array size is easier.

After finishing the program, prepare a short lab write up explaining your findings. Which sorting method seemed better? Did changing the size of the array effect the performance of the sorting method?

Turn in: source code output file short results write up


Bonus: 10% We discussed the technique of inserting values into an ordered list. (figuring where to insert, shifting the remaining values down one place, etc.) We also said that an array can be filled using the insertion algorithm. This method (sometimes called insertion sort) will fill the array and sort them at the same time. Implement this algorithm by inserting the values from the original unsorted array into a new ordered array using the insert algorithm. You will have to do the insertion sort before the selection sort on the first array. Keep track of swaps and compares as you did with the other algorithms. Include your results in your output and write up.

Explanation / Answer

#include<bits/stdc++.h>
using namespace std;

#define MAX_SIZE 500
void selectionSort(char array[], int &comparisons,int &swaps)
{
int l;
int index;

for(l = MAX_SIZE-1; l >= 1; l--)
{
index = 0;
for (int j = 1; j <= l; j++)
{
comparisons++;

if (array[j] > array[index])
{
index = j;
}
}
if (index !=l)
{
swap(array[l], array[index]);
swaps++;
}
}
}

void BubbleSort(char a[], int &comparisons,int &swaps)
{
   int n;
   int j;
   char temp;

   //start outer loop
   for (n=0; n < MAX_SIZE-1; n++)
   {
       //start inner loop
       for (j=0; j < MAX_SIZE-1; j++)
       {
           //compare adjacent values
           if (a[j] > a[j+1])
           {
               //swap values
               temp = a[j];
               a[j] = a[j+1];
               a[j+1] = temp;
swaps+=1;
           }
comparisons += 1;
       }
   }

}
int main(int argc, char const *argv[])
{
   char array[500],array1[500];
   int selection_comp=0,selection_swap=0;//maintain swap and comparison count for selection sort
   int bubble_comp=0,bubble_swap=0;//maintain swap and comparison count for bubble sort

   for (int i = 0; i < MAX_SIZE; ++i)
   {
       array[i] = 'A' + (random() % 26);//generate random character

      
   }
   strcpy(array1,array);

   cout<<"Unsorted Array is ";

   for (int i = 0; i < MAX_SIZE; ++i)
   {
       cout<<array[i]<<" ";

      
   }

   selectionSort(array,selection_comp,selection_swap);
   BubbleSort(array1,bubble_comp,bubble_swap);
cout<<" ======================================================== ";
   cout<<" Sorting using selection Sort ";
   for (int i = 0; i < MAX_SIZE; ++i)
   {
       cout<<array[i]<<" ";

      
   }
   cout<<" Comparison count of selection Sort "<<selection_comp<<endl;
   cout<<" Swap count of selection Sort "<<selection_swap<<endl;

cout<<" ======================================================== ";

cout<<" Sorting using Bubble Sort ";
   for (int i = 0; i < MAX_SIZE; ++i)
   {
       cout<<array1[i]<<" ";

      
   }
   cout<<" Comparison count of Bubble Sort "<<bubble_comp<<endl;
   cout<<" Swap count of Bubble Sort "<<bubble_swap<<endl;

   return 0;
}

============================================================

Output:

akshay@akshay-Inspiron-3537:~/Chegg$ g++ compare.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
Unsorted Array is
N W L R B B M Q B H C D A R Z O W K K Y H I D D Q S C D X R J M O W F R X S J Y B L D B E F S A R C B Y N E C D Y G G X X P K L O R E L L N M P A P Q F W K H O P K M C O Q H N W N K U E W H S Q M G B B U Q C L J J I V S W M D K Q T B X I X M V T R R B L J P T N S N F W Z Q F J M A F A D R R W S O F S B C N U V Q H F F B S A Q X W P Q C A C E H C H Z V F R K M L N O Z J K P Q P X R J X K I T Z Y X A C B H H K I C Q C O E N D T O M F G D W D W F C G P X I Q V K U Y T D L C G D E W H T A C I O H O R D T Q K V W C S G S P Q O Q M S B O A G U W N N Y Q X N Z L G D G W P B T R W B L N S A D E U G U U M O Q C D R U B E T O K Y X H O A C H W D V M X X R D R Y X L M N D Q T U K W A G M L E J U U K W C I B X U B U M E N M E Y A T D R M Y D I A J X L O G H I Q F M Z H L V I H J O U V S U Y O Y P A Y U L Y E I M U O T E H Z R I I C F S K P G G K B B I P Z Z R Z U C X A M L U D F Y K G R U O W Z G I O O O B P P L E Q L W P H A P J N A D Q H D C N V W D T X J B M Y P P P H A U X N S P U S G D H I I
========================================================

Sorting using selection Sort
A A A A A A A A A A A A A A A A A A A A B B B B B B B B B B B B B B B B B B B B B B B C C C C C C C C C C C C C C C C C C C C C C C D D D D D D D D D D D D D D D D D D D D D D D D D D D E E E E E E E E E E E E E E E F F F F F F F F F F F F F F F G G G G G G G G G G G G G G G G G G H H H H H H H H H H H H H H H H H H H H H H I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J J K K K K K K K K K K K K K K K K K K K L L L L L L L L L L L L L L L L L L L M M M M M M M M M M M M M M M M M M M M M M N N N N N N N N N N N N N N N N N N N O O O O O O O O O O O O O O O O O O O O O O O O P P P P P P P P P P P P P P P P P P P P P P Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q R R R R R R R R R R R R R R R R R R R R R S S S S S S S S S S S S S S S S S T T T T T T T T T T T T T T U U U U U U U U U U U U U U U U U U U U U U U V V V V V V V V V V W W W W W W W W W W W W W W W W W W W W W W W X X X X X X X X X X X X X X X X X X X X X Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Z Z Z Z Z Z Z Z Z Z Z Z
Comparison count of selection Sort
124750

Swap count of selection Sort
497

========================================================

Sorting using Bubble Sort
A A A A A A A A A A A A A A A A A A A A B B B B B B B B B B B B B B B B B B B B B B B C C C C C C C C C C C C C C C C C C C C C C C D D D D D D D D D D D D D D D D D D D D D D D D D D D E E E E E E E E E E E E E E E F F F F F F F F F F F F F F F G G G G G G G G G G G G G G G G G G H H H H H H H H H H H H H H H H H H H H H H I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J J K K K K K K K K K K K K K K K K K K K L L L L L L L L L L L L L L L L L L L M M M M M M M M M M M M M M M M M M M M M M N N N N N N N N N N N N N N N N N N N O O O O O O O O O O O O O O O O O O O O O O O O P P P P P P P P P P P P P P P P P P P P P P Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q R R R R R R R R R R R R R R R R R R R R R S S S S S S S S S S S S S S S S S T T T T T T T T T T T T T T U U U U U U U U U U U U U U U U U U U U U U U V V V V V V V V V V W W W W W W W W W W W W W W W W W W W W W W W X X X X X X X X X X X X X X X X X X X X X Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Z Z Z Z Z Z Z Z Z Z Z Z
Comparison count of Bubble Sort 249001

Swap count of Bubble Sort 57866

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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