Sort a string array without algorithm library

[jlmccart01]

How does one sort a string array given only these two parameters and not being allowed to use the algorithm library? I attempted to use anothers persons recommendation online, but quickly found that it wouldn't work with the parameters I have been given.

void arraySort(wordItem list[], int length)
{
      int i, j, swapV = 1;  
      int temp;         
      int numLength = length;
      for(i = 1; (i <= numLength) && swapV; i++)
     {
          swapV = 0;
          for (j=0; j < (numLength -1); j++)
         {
               if (list[j+1] > list[j])
              {
                    temp = list[j]; 
                    list[j] = list[j+1];
                    list[j+1] = temp;
                    swapV = 1;   
               }
          }
     }
}

[Manga]

A couple questions...

First, when you say sort, do you mean put them in alphabetical order?

And second, what is num.Length? Is it a global variable we can't see?

Third, you have int flag = 1, but it looks like you are using it like a Boolean expression. Was that your intention?

[jonnin]

whats a worditem?
assuming its some rename for "std::string", what does not work? Looks like a bubble sort for strings to me, and it looks correct without having any symptoms of the issue and not feeling like making it into a working program to test it...

[jlmccart01]

Sorry my bad. Let me explain. We are given a text file of words that we store in a vector. Then we have to sort this array by alphabetical order.

I was attempting a bubble sort from another post online, but I don't think it works since it is dealing with integers rather than strings.

So in my opinion all of this code is wrong logically. It may work on an integer array, but not a string array.

What I need to do is create a algorithm that just sorts the array by alphabetical order a-z. I unfortunately have no idea how to code something like that. Logically I would start with looking at each word and whether it starts with an a then look at the second character to see if it start with an or b and so on and so forth.

wordItem is a struct:

struct wordItem
{
    string word;
    int count;
};

EDIT: The online code runner thing says there is no operator >

prog.cpp:23:30: error: no match for 'operator>' (operand types are 'wordItem' and 'wordItem')
                if (list[j+1] > list[j])

[dhayden]

You need to look at the algorithm you downloaded and figure out how it works. Once you understand how it works with integers, you should be able to figure out how to make it work with wordItems.

You want to compare wordItems by the word within them:
if ((list[j+1].word > list[j].word)

Also, look at the variable temp. Figure out what it's used for. Then ask yourself if it has the right type for sorting wordLists and change it as appropriate.

[keskiverto]

wordItem foo;
wordItem bar;
bool fooLargerThanBar = foo > bar;

The operator> returns true, if the tested relation is true.

The wordItem was written by someone and an operator> has to be defined too; the compiler cannot invent that for you.

bool operator< ( const wordItem & lhs, const wordItem & rhs )
{
  return ...
}

[jonnin]

you have a few problems here. hopefully that string is std::string?! if not its going to be more work.

string has a length built into it, so the purpose of worditem is what? This is not looking correct.
string has a > operator built into it.
string has a = (assign) built into it.
methinks you should throw worditem in the garbage and sort strings, if you can.

if you MUST use the struct, you need to do 2 or 3 things.
1- temp must be a worditem (or if thrown out, string)
2 - if using worditem, you compare with array[x].word > array[x+1].word and it will work
3 - you may be able to assign word-item, I forget when the compiler is capable of making assignment operators and when it can't. If it can't, where-ever you assign one, you may need to do it field by field, eg array[x].word = array[y].word AND array[x].length = array[y].length. See if it works without that, though, I am 95% sure it will.

if you want PURE a-z sorting, you should compare toupper(array[x].word) > toupper(array[x+1.word). 'A' and 'a' are very different values when it sorts them and so forcing them all to be the same case is needed for pure sorting. Try it with and without that to see which you wanted. (I am weaker at text processing than most, toupper may be for char not string, but there is a string uppercase and string lowercase function out there if I got the wrong one).

[Manga]

@jonnin

string has a > operator built into it.

How do you get that to work?

[jonnin]

string a = "a";
string b = "b";
if(a<b)
cout << "a<b"<< endl;

here if he uses the struct, as I said, array[x].word < array[x+1].word (see above)
may want to make all the letters the same case, also said above.

you can also make comparison operator for the struct, someone showed that as well.

[Manga]

That is cool jonnin, but you are right about case being a problem.

So here is my attempt at a solution.

#include<iostream>
#include <string>
#include<vector>

using namespace std;

class word {
	string s;
public:
	word(const char a[]) {
		s = a;
	}

	bool operator < (const word &);
	friend void vectorSort(vector<word> &a);
	string getString() {
		return s;
	}
};

bool word::operator< (const word &w) {
	for (int i = 0; i < s.size() && i < w.s.size(); i++) {
		if (toupper(s[i]) < toupper(w.s[i])) {
			return true;
		}
		if (toupper(s[i]) > toupper(w.s[i])) {
			return false;
		}
	}
	if (s.size() < w.s.size()) {
		return true;
	}
	return false;
}

void vectorSort(vector<word> &a) {
	string temp;
	for (int i = 0; i < a.size(); i++) {
		for (int j = i + 1; j < a.size(); j++) {
			if (a[j] < a[i]) {
				temp = a[i].s;
				a[i].s = a[j].s;
				a[j].s = temp;
				j = i;
			}
		}
	}
}

int main()
{
	vector<word> myVector;
	myVector.push_back("banana");
	myVector.push_back("apple");
	myVector.push_back("orange");
	myVector.push_back("pear");
	myVector.push_back("grape");

	vectorSort(myVector);

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


	cin.get();
	return 0;
}

[jonnin]

something like that, yes.

Ill say again that your (and the OPs) word class is redundant though, just use string directly. String has char* interfaces, comparison, constructors, etc already. The class does not bring anything new -- the only reason for class word is to have it for a teacher's requirement. This is OSO (objects for the sake of objects) design, which some use, but to me all you get is code bloat.

[keskiverto]

The class does not bring anything new -- the only reason for class word is to have it for a teacher's requirement. This is OSO (objects for the sake of objects) design, which some use, but to me all you get is code bloat.

Yes and no.

It has not been told exactly, why struct wordItem exists. It might be that

struct wordItem { std::string word; int count; };

wordItem snafu[X];

could be replaced with
std::map<std::string,size_t> snafu;

However, we know that these programs are for sake of learning, and sorting structs is a learning experience. The std::map is entirely different thing to learn.

[jlb]

It looks like part of either this assignment or a future part of an assignment will be keeping track of the number of times the individual words occur within the "text".

The class does not bring anything new

Actually in this case using a "class" with the data using the default access method (private) brings added complexity that is probably just going to confuse things. Stick with the struct for now.

However since all of the OP's data members are public, you can still compare the strings inside the sort routine by directly accessing the string as has already been shown.

[Manga]

Well jonnin,

Shows what you know...

Wrapping the string in the class was not just pointless, it actually complicated the code ever so much so!!!

But near the end I was laughing at the entire ordeal. :P