Question

Need help with program. I'm stuck

Objectives: In this assignment, we will practice manipulating lists of data and arranging items in an ascending/descending order. you will also explore storing lists/arrays using different sorting algorithms including, the selection sort, bubble sort, and insertion sort algorithm. Comparison between the three algorithms are made based on the number of comparisons and item assignments (basic operations) each algorithms executes.

Background: Ordering the elements of a list is a problem that occurs in many computer science contexts for example, in a telephone directory it is necessary to alphabetize the names of subscribers. Similarly, creating a dictionary requires words be put in alphabetical order. While there are multiple sorting algorithms, some are better than others depending on the information being sorted. One thing in common which all sorting algorithms have is the sorting parameter. This “function” is what decides if two items in a list needs to switch places. While this is easy for the standard data types (int, char, double, …) since the compiler already knows how to compare these, it might be tricky for data types created by you. Structs and classes you create will require implementing comparison functions if you are trying to sort them. For example to compare two dates you can write something like:

bool compDate(Date d1, Date d2){

                  if (d1.year < d2.year

                        return true;

                  else if (d1.year == d2.year && d1.month < d2.month)

                        return true;

                  else if (d1.year == d2.year && d1.month == d2.month && d1.day < d2.day)

                        return true;

                  else

                        return false;

            }

The selection sort, bubble sort, and insertion sort algorithms are the most widely used algorithms. The section sort repeatedly picks the smallest element to append to the result. The insertion sort algorithm splits the list into two portions (sorted and unsorted) and repeatedly adds new element to the sorted portion of the list. The bubble sort algorithm repeatedly compares neighbor pairs and swap if needed.

Problem Description:

Write a C++ program to create 2 identical arrays, list1, and list2 – each list of 5000 elements. The program then sorts list1 using bubble sort, list2 using selection sort and outputs the number of comparisons and item assignments made by each sorting algorithm.

Hint: You need to create a random array and then copy it to end up with two identical lists (List1, List2). These two lists must be identical. You will need to sort List1 using bubble sort, and sort the second list List2 using the selection sort algorithm. Finally, you will need to output the number of comparisons and item assignments made by each sorting algorithm. Please note that the array should be randomly generated and you can do that by using the random function: rand() from the <cstdlib> library.

Sample:

IZACS250\A8_lab\bin\Debug\A8_lab.exe Number of comparisons--- Bubble sort: 12497500 Selection sort: 12497500 Insertion sort: 6404576 Number of item assignments--- Bubble sort: 19198794 Selection sort: 14997 Insertion sort: 6409574 Process returned 0 (0x0) Press any key to continue. execution time : 0.192 s

Answer 1

Source Code:

#include<iostream>
#include<cstdlib>
using namespace std;
int* bubblesort(int list[]);
int* selectionsort(int list[]);
int main()
{
   int n, i,list1[5000],list2[5000],r;
   for(i=0; i<5000; i++)
   {
   r = (rand() % 10) + 1;
       list1[i]=r;
       list2[i]=r;
   }
   int *bubble=bubblesort(list1);
   int *selection=selectionsort(list2);
   cout<<"Total comparisions: "<<endl;
   cout<<"Bubble sort= "<<bubble[0]<<endl;
   cout<<"selection sort= "<<selection[0];
   cout<<"\nTotal Assignment: "<<endl;
   cout<<"Bubble sort= "<<bubble[1]<<endl;
   cout<<"selection sort= "<<selection[1]<<endl;
   return 0;
}
int* bubblesort(int arr[])
{
   int i,j,comparision=0,assignments=0,temp;
   static int bubble[10];
   for(i=0; i<5000-1; i++)
   {
       for(j=0; j<(5000-i-1); j++)
       {
           if(arr[j]>arr[j+1])
           {
               temp=arr[j];
               arr[j]=arr[j+1];
               arr[j+1]=temp;
               comparision++;   //as there are singel comparision
               assignments+=3;   //as there are 3 time assign ments
           }
       }
   }
   bubble[0]=comparision;
   bubble[1]=assignments;
   return bubble;
}
int* selectionsort (int arr[])
{
   int i, j,comparision=0,assignments=0,min,loc,temp;
   static int selection[10];
   for(i=0;i<5000-1;i++)
{
min=arr[i];      
loc=i;
for(j=i+1;j<5000;j++)
{
if(min>arr[j])
{
min=arr[j];
loc=j;
comparision++;       //as there are singel comparision
assignments+=2;       //as there are 2 time assignments
}
}
temp=arr[i];
arr[i]=arr[loc];
arr[loc]=temp;
assignments+=5;   //as there are 5 time assignments in the for loop
}
selection[0]=comparision;
selection[1]=assignments;
return selection;
}  

Output: