Insertion Sort in a Class?

Question

I'm a Cpp newbie and I have a question that i can't find an answer to it. So Im writing this program about Tourist sights using a class. Inside i have name of the sight, addres and distance from the city center. All i've done is the input and output. Now i have no idea how to sort them with InsertionSort. Do I need another array? I want to sort them by distance but have no idea how to write it.

Here is what i have

#include <iostream>
#include <string>
using namespace std;
class Tobekt {
  private: string name;
          string addres;
          int distance;


  public:
    void input(void);
    void output(void);
}; 

void Tobekt::input(){

   cout<<"Landmark name: ";
   getline(cin, name);
   getline(cin, addres);
   cout<<"Addres: "; 
    getline(cin, addres);
    cout<<"Distance from the city center:  ";
    cin>>distance;
}
void Tobekt::output(){
    cout<<endl;
    cout<<"Landmark name: "<<name<<endl;
   cout<<"Addres: "<<addres<<endl; 
    cout<<"Distance from the city center: "<<distance<<endl;

}

int main()
    { 
    int n;
    cout<<"Tourist landmarks:" ;
    cin>>n;
    Tobekt *A = new Tobekt[n];
    for(int i=0; i<n; i++)
    {
        A[i].input();
    }
    for(int i=0; i<n; i++)
    {
        A[i].output();
    }

return 0;
    }

use a `std::vector`. `new` without `delete` is a memory leak. `new` with `delete` is still a potential memory leak. You dont need any manual memory managment here — 463035818_is_not_an_ai, Nov 28 '18 at 15:54
*Now i have no idea how to sort them with InsertionSort.* -- You didn't show any attempt, and we have no idea what type of help you are asking for (you're not asking a focused question). Anyway [here is a link](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). — PaulMcKenzie, Nov 28 '18 at 15:57

Davide Spataro · Answer 1 · 2018-11-28T16:10:06.533

You can simply sort the array using the sort algorithm that you have in the standard library and provinding a custom sorting criteria. In the following for instance the sights are sorted by distance.

auto sort_criteria=[](const auto& a, const auto&b){
return a.distance < b.distance;
};

int main()
    { 
      Tobekt *A = new Tobekt[n];
      //read input
       sort(A, A+n, sort_criteria);
      //other stuff
    }

score 2 · Answer 2 · answered Nov 28 '18 at 16:09

Insertion Sort's algorithm do not require a new array for sorting. The idea behind insertion sort is to loop through the array twice.

First Loop is to loop through the "unsorted" elements in the array and pick the first "unsorted" element.
Second Loop is to compare that element with the previous "sorted" elements - if its "smaller", move the element towards your start of the array index and repeat until it cannot be moved.

You can visit this link to get a better visualization of how it works. As such, you may need a function that performs the comparison function. Something like...

bool SmallerDistance(const Tobekt& lhs, const Tobekt& rhs)
{
    return lhs.GetDistance() < rhs.GetDistance();
}

Of course, you would need to create getter function to get the distance from the class. Alternatively, you could always create the operator< member function and compare with two variables.

P.S. Do remember to delete A variable after you new or you will have memory leak for your program.

score 0 · Answer 3 · answered Nov 28 '18 at 16:50

You might find the book of R. Lafore "Algorithms & Data Structures in Java" useful. There are two chapters on sorting algorithms including insertion sort with relevant code snippets. (It says Java, but the syntax in Java is close to C++, and there's a section in the book that discusses differences between the two languages.)

Insertion Sort in a Class?

3 Answers3