Using struct with an insertion sort

Question

I'm having some trouble with an insertion sort, passing in data from a struct. It's returning the error: |98| cannot convert 'store' to 'int' in assignment.

struct store{
    char tag[5];
    int cost;
    long int volume;
};


void costSort(store storedEntries[], int count);
void volumeSort(store storedEntries[], int count);

int main(){

    store record[100];
    ifstream fin;
    char choice;
    int count = 0;

    fin.open("stockdata.txt");

    //file read in
    if(fin.good())
    {
        while(!fin.eof())
        {
            fin >> record[count].tag;
            fin >> record[count].cost;
            fin >> record[count].volume;
            count++;
        }
    count--;
    }


    cout << "Main Menu:" << endl;
    cout << "c: sort data by Cost\nv: sort data by trade Volume\nq: Quit\nEnter Choice: ";

    cin >> choice;

    switch(choice)
    {
        case 'C':
        case 'c': //costSort(record, count);
            break;
        case 'V':
        case 'v': volumeSort(record, count);
            break;
        case 'q':
        case 'Q': return 0;
            break;
    }
   return 0;
}

void volumeSort(store record[], int count)
{
    int p = 0, item = 0;

    for(int i=1; i<count; i++){
    cout << "test";
        item = record[i];
        p = (i - 1);
        while(p>=0 && item < record[p]){
            record[p+1] = record[p];
            p--;
        }
        record[p+1] = item;
        cout << record[i].tag << " " << record[i].volume << endl;
    }

}

The insertion sort is in the function void volumeSort(). Any advice would be appreciated, i haven't had any issues up until now :S

Fyi, [this is wrong: **`while(!fin.eof())`**](https://stackoverflow.com/questions/5605125/why-is-iostreameof-inside-a-loop-condition-considered-wrong). — WhozCraig, Mar 26 '15 at 06:25
Welcome here, please post the code where the error is detected. — philant, Mar 26 '15 at 06:25
Thanks for the heads up, any advice on the insertion sort? @philant, the code where the error is detected is in the function volumeSort. line "item = record[i];" — Cirrus, Mar 26 '15 at 06:26
`item = record[i]` is certainly wrong; `item` is `int`, `record[i]` is `store`. Likewise with `item < record[p]`. And `record[p+1] = item`, equally wrong. — WhozCraig, Mar 26 '15 at 06:27

score 1 · Answer 1 · edited Mar 26 '15 at 07:19

1

You are trying to compare a int with a store.

This will not work unless you overload < operator to compare a int and a store.

store record[];
int p = 0, item = 0;
//[...]
while (p >= 0 && item < record[p])
//Neither can you assign that
record[p + 1] = item;

Operator example:

bool operator<(const int &left, const store &s)
{
    //You could also do some calculation in here,
    //if you want to compare a value inside the struct
    //like this:
    return left < s.cost;
    //Please... do it in place.
    //item < record[p].cost;
}

edited Mar 26 '15 at 07:19

shauryachats

9,975
4
35
48

answered Mar 26 '15 at 06:27

Blacktempel

3,935
3
29
53

What do you mean by "an own operator"? I''ve tried changing the int values to store and visa versa with no luck – Cirrus Mar 26 '15 at 06:32
You could write a `operator<` function which takes a `int` and a `store` and compare both, based on one of the values in your `store` or like you wish to compare them. But you cannot compare two completely different types. This will simply not work. – Blacktempel Mar 26 '15 at 06:37
@Cirrus Updated my answer with a `operator<` example. – Blacktempel Mar 26 '15 at 06:40
Fwiw I see no earthly sense in writing an operator < for what is ultimately supposed to be comparing two members of two structures indexed by two indexes. Operator overloading isn't something you do because you *can*; you do it because you *should*. – WhozCraig Mar 26 '15 at 06:46
@WhozCraig Of course it makes no sense here. But I have no idea what he is actually trying to achieve. Most likely test code... so at least he does know now, how he COULD overload a operator. - Updated answer... – Blacktempel Mar 26 '15 at 06:48

WhozCraig · Answer 2 · 2015-03-26T07:17:37.123

You're comparing non-like types with no operator provided to support the comparison (and none needed if this is done correctly). Currently you're comparing int to store. What you should be comparing is two volume members of two store objects.

A simple loop that is probably closer to what you want would be something like this:

// note: count is size_t, an unsigned magnitude. only used signed
//  integer types where it makes sense a negative integer will be
//  plausible input.
void volumeSort(store record[], size_t count)
{
    for(size_t i=1; i<count; ++i)
    {
        // compare current element to one below us, swapping if needed
        // and stopping as soon as we reach an equal or lesser record
        size_t j=i;
        while(j>0 && record[j].volume < record[j-1].volume)
        {
            std::swap(record[j-1], record[j]);
            --j;
        }
    }
}

Or something similar. Note the comparison of:

record[j].volume < record[j-1].volume

in the while condition. Apples to apples...

For an interesting insertion_sort that utilizes two wonderful features of the standard library, std::upper_bound and std::rotate, a rather dense version of the function can be created, looking something like this:

void insertion_sort(store record[], size_t len)
{
    for (auto it = record; it != record+len; ++it)
    {
        std::rotate(std::upper_bound(record, it, *it,
            [](const store& lhs, const store& rhs) { return lhs.volume < rhs.volume; }),
            it, std::next(it));
    }
}

This is considerably more efficient than it first may seem, as the search for the proper placement of the prospect element is done in O(logN) using std::upper_bound. Then std::rotate opens the hole where the element goes and it is swapped into place.

Just some food for thought. Coupled with the comparator that is going to inlined by even remedial optimization and it has a lot more punch than you may first think. Still not as kick-ass as std::sort, usually highly optimized utilizing multiple algorithms, but still good brain food.

Best of luck.

score 0 · Answer 3 · answered Mar 26 '15 at 06:37

0

if you want to sort by volume you should take record[i].volume even when comparing...the types should be same when comparing values..

Similarly for other cases..

answered Mar 26 '15 at 06:37

DeepN

344
2
13

Using struct with an insertion sort

3 Answers3