Sorting a suffixarray

This is a discussion on Sorting a suffixarray within the C++ Programming forums, part of the General Programming Boards category; Hello, I've implemented an suffixarray, wich then I sort with bubblesort. To improve it a bit, I'm trying to get ...

  1. #1
    Registered User
    Join Date
    May 2005
    Location
    Germany
    Posts
    12

    Question Sorting a suffixarray

    Hello,

    I've implemented an suffixarray, wich then I sort with bubblesort. To improve it a bit, I'm trying to get the stable_sort() function to work, without success...

    I've read, the stable_sort() should get as first argument the name of the array to sort, as second the number of the max. elements the array can hold. This doesn't work in this case, or am I doing something wrong?

    It would be great if someone could give me a hint.

    Here is the code for the sort function:
    Code:
    /***
     * Sorting Algorithm
     */
    	void sort() {							
    //		stable_sort(this->suffix, (this->suffix)+lastcell+1);
    //		cout << "Sorting finished " <<endl;
    	}
    And here is the suffixarrayclass:
    Code:
    class suffixarray {
    	private :	static const int max = 100000;			//Maximum entries in the suffixarray
    			int suffix[max][2];			// [max][0]= TextArray [max][1]=Suffixarray
    			int	lastcell;
    			dictionary *dict;
    	public :
    /**
     * Constructor reads all words from textfile
     * 
     * @param filename of the textfile
     */
    	suffixarray(string filename) {
    		cout << "Start reading from file " << filename  << "\nPlease stand by!" <<endl;
    		for (int i = 0; i< max; i++) {
    			this->suffix[i][0] = -1;		//Text
    			this->suffix[i][1] = -1;		//Suffix
    		}
    		this->dict = new hashtable();
    									//Create new dictionary
    		string word = "", output = "";				//initialise vars
    		fstream inputFile(filename.c_str());
    		unsigned int total = 0, i = 0;
    		char ch;
    		while(inputFile >> word) {				//read each word
    			output = "";
    			for (i = 0; i < word.length(); i++) {		//read each char
    				ch = word[i];
    				if ( !isalnum(ch) ) {			//exclude special chars
    					output = ch;
    					this->suffix[total][0] = this->dict->enterWord(output);
    					this->suffix[total][1] = total;
    					output = "";
    					total++;
    				} else {				//get complete words
    					// Add chars to the output-Str till an spec.char comes
    					//take care of words like "half-duplex"
    					while( isalnum(ch) || ( ch == '-' && isalnum(word[i+1])) ) {
    						output += ch;
    						i++;
    						ch = word[i];
    					}
    					i--;
    					this->suffix[total][0] = this->dict->enterWord(output);
    					this->suffix[total][1] = total;
    					output = "";
    					total++;
    				}
    			}
    		}
    		this->lastcell = total-1;				//set last not-empty cell
    		cout << "Reading finished with "<<total
    			<<" words\nWords in Dictionary: "
    			<< 9973 - this->dict->emptyOnes() <<endl;
    		this->sort();
    	}
    /**
     * Destructor
     */
    	~suffixarray() {
    		delete this->suffix;
    		delete this->dict;
    };
    Last edited by kapri; 05-29-2005 at 03:34 PM.

  2. #2
    Registered User
    Join Date
    May 2005
    Location
    Germany
    Posts
    12
    I've got now, a not so efficient solution that works. You can copy the content of suffix[i][1] to another array temp[asBigAsSuffix], sort temp with stable_sort() and copy the results back. I will still try to get stable_sort() to work with suffix as it should.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 05:50 PM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM
  5. selection sorting
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-13-2001, 08:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21