Insert-sort a 2D Vector of characters

[herad]

I have built a 2D vector of characters such as this:

Apple
Fruit
Banana
apple
4apples
3bananas

Where each line is the first dimention of the vector and each column contains the char.

I print the 2D vector like this:

 vector<vector<char>> vsort;
	for (vector<vector<char>>::size_type i = 0; i < vsort.size(); ++i)
		{
			for (vector<vector<char>>::size_type j = 0; j < vsort[i].size(); ++j)
			{
				  cout << vsort[i][j] << " ";
			}
			cout << endl;
		}
	

I need to do a insert-sort on the Vectors besides using the already included sort(). The problem because I am dealing with a 2D vector with characters I am not sure how to approach it. Each vector should be sorted based on the ASCII table as if I got the same output by using sort(). Any help please?

[jlb]

Is there a particular reason that you chose a std::vector<std::vector<char>> instead of just a std::vector<std::string>?

What exactly are you trying to "sort"? The inner or outer vector?

[herad]

Is there a particular reason that you chose a std::vector<std::vector<char>> instead of just a std::vector<std::string>?

I use std::vector<std::vector<char>> because I thought it would be easier for sorting, and that I use vector operations like rotate() for the characters. Later on I would need to get the last characters for each of the vectors which is why I though 2D would be better.
So the outer vector I assume which already contains the "strings" is the one I am trying to sort. Example is:

Apple
Fruit
Banana
apple
4apples
applesauce
3bananas
"apple"

sorted to

"apple"
3bananas
4apples
Apple
Banana
Fruit
apple
applesauce

[jlb]

I really recommend that you consider using a std::string instead of the vector<char>. The std::string has quite a few "helper functions" to make most of the things you're trying to do easier.

that I use vector operations like rotate() for the characters

Do you realize that you can use std::rotate() with a std::string?

Later on I would need to get the last characters for each of the vectors which is why I though 2D would be better.

Do you realize that a std::string knows it's size and that it is quite simple to determine the length and to find the last character?

I need to do a insert-sort on the Vectors besides using the already included sort(). The problem because I am dealing with a 2D vector with characters I am not sure how to approach it.

Do you realize that std::string has builtin comparison operators? Using these operators along with the std::vector.insert() and std::vector.push_back() should help make the insertion sort easier (IMO).

So the outer vector I assume which already contains the "strings" is the one I am trying to sort.

If your outer vector is a vector<char> you don't have strings, you have a vector of single characters, don't confuse this with a string. Remember to properly sort a vector<char> you will probably need to individually check multiple characters to see that they match. With a std::string all you need to do is check the strings.

[George P]

Use a std::set (or std::multiset if you want to have duplicates), instead of using a std::vector, to hold std::strings and you automatically get the list sorted when you add items.

https://en.cppreference.com/w/cpp/container/set/set

[Duthomhas]

String would have been a better choice but vector is not wrong. Rather try to dissuade OP from all his design choices (and rather than suggest designs of increasing complexity), consider that OP has asked specifically about an insertion sort...

Maybe there are design issues that we are unaware of because this is part of a homework? Or even a self-study?

Insertion. Sort is really simple to implement. (Less simple to implement really efficiently, but not that difficult.) And it will work just fine over vector/string/whatever. It is basically a find-minimim and rotate in linear complexity.

Give a sec and I'll edit with a link to the FAQ on insertion sort.

http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/insertion-sort/

Hope this helps

[herad]

Alright so I just updated my entire project so now it is using vector<string> instead of vector<vector<char>>.

I tried the operations like rotate for strings and they did seem to work like they did with the vector of characters. It looks easier now with a string vector than a 2D. I'm not sure why I didn't thought of this before.

So , here's what I tried:

void insertionSort(vector<string> v){

	for (int i = 1; i < v.size(); i++) {
	        for (int j = i; j > 0 && v[j - 1] > v[j]; j--) {
	            string tmp = v[j];
	            v[j] = v[j - 1];
	            v[j - 1] = tmp;
	        }
	    }

}

int main() {
	vector<string> v = {"Apple", "Fruit", "Banana", "apple", "4apples", "applesauce", "3bananas", "\"apple\""};


	//  Print original vector
		cout << "******Original*******"<< endl;
		for (vector<string>::size_type i = 0; i < v.size(); ++i)
		{
				  cout << v[i] << endl;
		}


		//Do insertionSort
		insertionSort(v);

	//  Print sorted vector
       	   cout << "******SORTED*******"<< endl;
   		for (vector<string>::size_type i = 0; i < v.size(); ++i)
   		{
   				  cout << v[i] << endl;
   		}

But the output does not seem to change.

[Duthomhas]

You are passing the vector argument by value -- it will not modify the original vextor.

Either return a new vector as result or pass by reference. I reccomend the second option:

Void insertionsort( vector<string>& v )


BTW, your sort function is doing TWO things, one of which has. Ithing to do with sorting. May I recommend being a little more pedantic about separation of responsibilities?

void insertionsort( string& xs ) ...

And use it in a loop over your vector:

for (auto& elt : v) insertionsort( elt );


Finally, if you wish, you can write your sort to work over any container using templates:

template <typename Container>
void insertionsort( Container& xs )


On my phone... sorry for the poorly- formatted post, and I haven't looked at your code really...

Hope this helps anyway