Implement the selection sort algorithm to sort a vector in a

Implement the selection sort algorithm to sort a vector<TokenFreq> in ascending order of token frequency.

This function has the following prototype:

void selectionSort( vector<TokenFreq> & tokFreqVector ); This function receives a vector of TokenFreq objects by reference and applies the selections sort algorithm to sort this vector in increasing order of token frequencies.

Solution

The c++ program initializes the vector<TokenFreq> with some sample values. Class TokenFreq has two members, a) A string token and b) Frequency of this token. vector<TokenFreq> is a vector of TokenFreq objection.  

The code and output is presented here. The comments in the code have been added for better understanding.

----------------------------------------------------------------------------------

C++ Code:

#include <iostream>
#include <vector>

using namespace std;

// Token fequency class
class TokenFreq{
public:
    string token; // string token
    int freq;     // frequency of token
};

// Selection sort to sort the vector
void selectionSort(vector<TokenFreq> &tokFreqVector){
int i,j;
int min;
TokenFreq temp; // temp object
int n=tokFreqVector.size(); // length of vector

// Two nested for loops
for(i=0; i<n-1; i++){
    min=i; // suppose i is minimum
    for(j=i+1; j<n; j++){
      if(tokFreqVector[j].freq < tokFreqVector[min].freq){ // check to find minimum frequency
        min=j;
      }
    }
  
    // swap is min!=i
    if(min!=i){
      temp=tokFreqVector[min];
      tokFreqVector[min]=tokFreqVector[i];
      tokFreqVector[i]=temp;
    }
}
}

int main(){
vector<TokenFreq> v;

// TokenFreq object
TokenFreq *tf = new TokenFreq[5];
tf[0].token = \"token1\";
tf[0].freq = 65;
tf[1].token = \"token2\";
tf[1].freq = 15;
tf[2].token = \"token3\";
tf[2].freq = 43;
tf[3].token = \"token4\";
tf[3].freq = 50;
tf[4].token = \"token5\";
tf[4].freq = 29;

// Push it into the vector
v.push_back(tf[0]);
v.push_back(tf[1]);
v.push_back(tf[2]);
v.push_back(tf[3]);
v.push_back(tf[4]);

cout << \"\ Before selection sort: \ \" << endl;
int n = v.size();

for(int i=0; i<n; i++){
    cout<< \"Frequency: \" << v[i].freq << \" of \" << v[i].token << endl;
}
cout << \"----------------------\" << endl;

selectionSort(v);

cout << \"\ After selection sort: \ \" << endl;
for(int i=0; i<n; i++){
    cout<< \"Frequency: \" << v[i].freq << \" of \" << v[i].token << endl;
}
cout << \"----------------------\" << endl;
return 0;
}

----------------------------------------------------------------------------------

OUTPUT:

Before selection sort:

Frequency: 65 of token1
Frequency: 15 of token2
Frequency: 43 of token3
Frequency: 50 of token4
Frequency: 29 of token5
----------------------

After selection sort:

Frequency: 15 of token2
Frequency: 29 of token5
Frequency: 43 of token3
Frequency: 50 of token4
Frequency: 65 of token1
----------------------