Objectives: Explore how to sort an array using selection sort and insertion sort
ID: 3774652 • Letter: O
Question
Objectives:
Explore how to sort an array using selection sort and insertion sort algorithms.
Question:
Write a program that allows the user to enter the last names of five candidates in a local election and the number of votes received by each candidate. The program should then output each candidate’s name and the number of votes received, in a descending order.
1. Use selection sort to achieve this.
2. Use insertion sort to achieve this.
I already have the main function. I just need the selection and insertion functions.
Code so far:
#include <iostream>
#include <string>
using namespace std;
void selectionSort(int vote[], string name[], int len);
void insertionSort(int vote[], string name[], int len);
int main() {
string *name;
int *vote;
name=new string[5];
vote=new int[5];
for(int i=0; i<5;i++){
cout<<"Please input candidate "<<i+1<<" name: "<<endl;
cin>>name[i];
cout<<"Please input candidate "<<i+1<<" votes: "<<endl;
cin>>vote[i];
}
//Q1 or Q2
selectionSort(vote, name, 5);
//insertionSort(vote, name, 5);
cout<<"Candidate "<<"Votes Received "<<"%"<<endl;
for(int i=0; i<5; i++){
cout<<name[i]<<" "<<vote[i]<<" "<<endl;
}
cout<<"The winner of the election is "<<name[0]<<endl;
delete []name;
delete []vote;
return 0;
Output:
Please input candidate 1 name:
a
Please input candidate 1 votes:
1
Please input candidate 2 name:
b
Please input candidate 2 votes:
2
Please input candidate 3 name:
c
Please input candidate 3 votes:
3
Please input candidate 4 name:
d
Please input candidate 4 votes:
4
Please input candidate 5 name:
e
Please input candidate 5 votes:
5
Candidate Votes Votes Recieved %
e 5
d 4
c 3
b 2
a 1
The winner of the election is e
Explanation / Answer
#include <iostream>
#include <string>
using namespace std;
void selectionSort(int vote[], string name[], int len);
void insertionSort(int vote[], string name[], int len);
int main() {
string *name;
int *vote;
name=new string[5];
vote=new int[5];
int total=0;
for(int i=0; i<5;i++){
cout<<"Please input candidate "<<i+1<<" name: "<<endl;
cin>>name[i];
cout<<"Please input candidate "<<i+1<<" votes: "<<endl;
cin>>vote[i];
total+=vote[i];
}
//Q1 or Q2
//selectionSort(vote, name, 5);
insertionSort(vote, name, 5);
cout<<"Candidate "<<"Votes Received "<<"%"<<endl;
for(int i=0; i<5; i++){
cout<<name[i]<<" "<<vote[i]<<" "<<(vote[i]*100)/total<<endl;
}
cout<<"The winner of the election is "<<name[0]<<endl;
delete []name;
delete []vote;
return 0;
}
//function to sort array using selction algorithm
// In selection sort, the strategy is to find the smallest number in the array and exchange it with the value in first position of array.
//Now, find the second smallest element in the remainder of array and exchange it with a value in the second position, carry on till you have reached the end of array.
void selectionSort(int vote[], string name[], int len)
{
int min,loc,temp;
string tempname;
for(int i=0;i<len-1;i++)
{
min=vote[i];
loc=i;
for(int j=i+1;j<len;j++)
{
if(min<vote[j])
{
min=vote[j];
loc=j;
}
}
temp=vote[i];
vote[i]=vote[loc];
vote[loc]=temp;
tempname=name[i];
name[i]=name[loc];
name[loc]=tempname;
}
}
//In insertion sort, we assume that first element A[0] in pass 1 is already sorted.
//In pass 2 the next second element A[1] is compared with the first one and inserted into its proper place either before or after the first element.
//In pass 3 the third element A[2] is inserted into its proper place and so on.
void insertionSort(int vote[], string name[], int len)
{
int temp,j;
string tempname;
for(int i=1;i<=len-1;i++)
{
temp=vote[i];
tempname=name[i];
j=i-1;
while((temp>vote[j])&&(j>=0))
{
vote[j+1]=vote[j]; //moves element forward
name[j+1]=name[j];
j=j-1;
}
vote[j+1]=temp; //insert element in proper place
name[j+1]=tempname;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.