sorting data

[eXord]

Hey guys, so I'm in a pickle... I'm trying to write a program to sort data as it's being read. At the moment I have a program which reads a list of words from a text file into an array. I know it would probably be easier to be sorted after the whole file is read in but I want to sort the data as it's being read in.

I searched the webs for help and managed to code a simple selection sort but I'm having trouble implementing this sort into my program!

       code removed
	}

And here's my code... I've already played around with merging/implementing the sort with my code, but to no avail. My program hangs, does nothing and crashes. Any help would be much appreciated guys :)

        code removed

Thanks guys :)

[MiiNiPaa]

You can use set container type, which keeps values sorted as you add them:
http://en.cppreference.com/w/cpp/container/set

[cire]

Sorting isn't really a word that applies here. What you're doing is inserting items into an ordered sequence while maintaining the order.

Using a vector:

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>

void insert_ordered(std::vector<std::string>& words, const std::string& word)
{
    if (words.size() == 0 )
        words.push_back(word) ;
    else
        words.insert( std::lower_bound(words.begin(), words.end(), word), word ) ;
}

int main()
{
    using namespace std ;

    ifstream fin("words.txt") ;
    vector<std::string> words ;

    if(!fin.is_open())
    {
        cout << "Error opening file" << endl;
        return 0 ;
    }

    string word ;
    while ( fin >> word )
        insert_ordered(words, word) ;

    for (int i = 0; i < words.size(); ++i)
        cout << words[i] << endl;
}

[edit: formatting]

[eXord]

hi, thanks for your reply. Thanks for the help, helped me sort of understand what needs to be done. However, I need to be able to do this with an array, rather than a vector. Is it possible to be able to do what you have done there with an array?

[cire]

Is it possible to be able to do what you have done there with an array?

Not exactly, no, but you can get the job done. You removed your original code (why? it is considered rude), so I don't have anything to work with as far as the solution you've already attempted.

You will need an array. A constant (or variable if you're using a dynamically allocated array) that tracks the capacity of the array, and a variable that represents the number of objects currently stored in the array.

You'll need code that performs the equivalent of lower_bound (which is really a very simple thing to do) and one which inserts an element into an array at a specific index or location (and remember to update the variable representing the number of objects stored in the array when one is inserted.)

lower_bound's description can be found on this site by using the search function or accessing the "Documentation" link on the upper left side of the screen. The search is probably more straightfoward than navigating the documentation.

[eXord]

Hey, sorry about removing the code, I thought the thread had died, but thanks for keeping it alive! :)

// 

Here's my code. I've done some searching for 'lower bound' and 'insertion' implementation for arrays and most results lead me to very complex implementations or irrelevant stuff to what I'm looking for which just goes way over my head at the moment.

Any help would be great, and sorry again about the code removal! :)

[cire]

Say you have a sorted array of characters:

char array[suitably_large_number] = { 'a', 'c', 'y', 'z' }

and you want to insert 'd'.

We can see just by looking that the insertion point is going to be between the 'c' and the 'y', but how do you determine that programmatically? Well, we're going to iterate through the array and look for the first character that is greater than 'd'. That character is going to be in the position we want our 'd' to be in. This is actually what upper_bound does. It returns an iterator to the first element it encounters that is greater than the element we want to insert. (lower_bound returns an iterator that points to the first element it encounters that is greater than or equal to the element we want to insert. Either would work here, but upper_bound is going to be slightly more efficient.)

A simplified version of upper_bound (for the problem just described) might look like this:

char* upper_bound(char* begin, char* end, char element)
{
    char * current = begin ;
    while ( current != end )
    {
        if ( *current > element )
            break ;
        ++current ;
    }

    return currrent ;
}

So, now that we've found the insertion point, we need to move all elements at or to the right of the insertion point one element to the right, and make room for the element we want to insert. With the std library you could use std::copy_backward, note that std::copy isn't appropriate because the source and destination areas overlap.

Here is code using std::upper_bound and std::copy_backward. I've made an assumption based on your code (that the number of words in the file is on the first line of the file) which may cause problems if it isn't correct.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>


void insert_ordered(std::string* words, const std::string& word, unsigned nWords )
{
    if ( nWords == 0 )
        words[0] = word ;
    else
    {
        std::string* ub = std::upper_bound(words, words+nWords, word) ;     // find the insertion point.

        if ( ub != words+nWords )                                           // if the insertion point is not the
            std::copy_backward(ub, words+nWords, ub+1) ;                    // end of the array, move some stuff.

        *ub = word ;
    }
}

int main()
{
    using namespace std ;

    ifstream fin("words.txt") ;

    if(!fin.is_open())
    {
        cout << "Error opening file" << endl;
        return 0 ;
    }

    unsigned totalWords ;
    fin >> totalWords ;

    std::string* words = new std::string[totalWords] ;
    unsigned nWords = 0 ;

    string word ;
    while ( fin >> word )
        insert_ordered(words, word, nWords++) ;

    for (int i = 0; i < nWords; ++i)
        cout << words[i] << endl;
}

[Cubbi]

I always find it funny that, when dealing with overlapping ranges, copy_backward() is the one that can copy to the right (forward!), while copy() can copy to the left (backward)