Sorting words, stuck in infinite loop.

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 1584 Views - Last Post: 05 June 2011 - 12:38 PM Rate Topic: -----

#1 AgentSmith  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 04-June 11

Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 05:00 PM

Hello there,
I am a C++ beginner experimenting with strings,arrays,etc...I am trying to create a program that sorts words in alphabetical order (came up with the idea myself). I have been told there are programs out there already like bubble-sort, but I am not cheating I want to make this one on my own. The program below isn't complete, it is only supposed to sort by looking at the first letter, but even then it is stuck in some infinite loop. Any ideas would be appreciated, thanks!

#include <iostream>
#include <string>

using namespace std;

int main()
{
int arr_size;
cout << "Please enter how many words you would like to sort...\n";
cin >> arr_size;
string * items1 = new string [arr_size];
cout << "Please enter words to sort...\n";

int i_counter;

for (i_counter=0; i_counter < arr_size; i_counter++) 
{
	cin >> items1[i_counter];
} 
for (i_counter=0; i_counter < arr_size; i_counter++)
{
	cout << items1[i_counter] << "\n";
}

/* Now let us sort these words */
cout << "Here are the words in alphabetical order \n";
bool chaos=true; 

do
{
	
	for(i_counter=0;i_counter < arr_size;i_counter++)
	{
		string temp;
		string temp1;
		
			temp=items1[i_counter];
			temp1=items1[i_counter+1];
			chaos=0;
		
			if (temp[0] > temp1[0])
			{
				items1[i_counter]=temp1;
				items1[i_counter]=temp;
				chaos=1;
			}	
		
			else if (temp[0] == temp1[0])
			{
				chaos=1;
				// More advanced code here later
			}
			
			else
			{
				break;
			}
	}
				
}while(chaos==1);

for (i_counter=0; i_counter < arr_size; i_counter++)
{
	cout << items1[i_counter] << "\n";
}

return 0;
}



This post has been edited by AgentSmith: 04 June 2011 - 05:02 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Sorting words, stuck in infinite loop.

#2 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 05:19 PM

explain your algorithm in English. post it in bullet format, that is what you need to do first. also IMO it's not cheating to simply implement an already established algorithm.
Was This Post Helpful? 0
  • +
  • -

#3 AgentSmith  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 04-June 11

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 05:27 PM

View Postishkabible, on 04 June 2011 - 05:19 PM, said:

explain your algorithm in English. post it in bullet format, that is what you need to do first. also IMO it's not cheating to simply implement an already established algorithm.


  • The program asks how many words to sort, this is used to create an array of strings.
  • After the user inputs the words, the double loop begins to run.
  • The inner loop goes down the list of words and switches words, 1 by one, by looking at the first letter.
  • Running this once will not arrange all the words, but if we run this enough times, eventually the order should be alphabetical, the outer loop controls how many times the inner loop runs.
  • The outer loop looks at the "chaos" flag which is set to true initially. The inner loop sets the flag to false, but as soon as it encounters a switch to be made it changes the flag to true, making the inner loop run again next time, this is done until the inner loop finds no changes to be made.

This post has been edited by AgentSmith: 04 June 2011 - 05:28 PM

Was This Post Helpful? 0
  • +
  • -

#4 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 05:38 PM

well instead of comparing the indexs maybe you could just use std::string::operator< or in other words the "<" operator :)

std::string s1("abc"), s1("bcd")
if(s1 < s2) {
   std::cout<<"hey look at that :)/>"<<std::endl;
}


Was This Post Helpful? 0
  • +
  • -

#5 AgentSmith  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 04-June 11

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 05:52 PM

I did not know you can compare strings that way, but I modified the code to this, still in infinite loop. I've been staring at this code for hours XD.



#include <iostream>
#include <string>

using namespace std;

int main()
{
int arr_size;
cout << "Please enter how many words you would like to sort...\n";
cin >> arr_size;
string * items1 = new string [arr_size];
cout << "Please enter words to sort...\n";

int i_counter;

for (i_counter=0; i_counter < arr_size; i_counter++) 
{
	cin >> items1[i_counter];
} 
for (i_counter=0; i_counter < arr_size; i_counter++)
{
	cout << items1[i_counter] << "\n";
}

/* Now let us sort these words */
cout << "Here are the words in alphabetical order \n";
bool chaos=true; 

do
{
	
	for(i_counter=0;i_counter < arr_size;i_counter++)
	{
		string temp;
		string temp1;
		
			temp=items1[i_counter];
			temp1=items1[i_counter+1];
			chaos=0;
		
			if (temp > temp1)
			{
				items1[i_counter]=temp1; 
				items1[i_counter]=temp;
				chaos=1;
			}	
		
			else if (temp[0] == temp1[0])
			{
				chaos=1;
				// More advanced code here later
			}
			
	}
				
}while(chaos==1);

for (i_counter=0; i_counter < arr_size; i_counter++)
{
	cout << items1[i_counter] << "\n";
}

return 0;
}


Was This Post Helpful? 0
  • +
  • -

#6 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 05:56 PM

show me where this exits the loop first. show me the line of code that is responsible for causing the loop to exit.
Was This Post Helpful? 0
  • +
  • -

#7 AgentSmith  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 04-June 11

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 06:05 PM

For the inner loop it should exit when i_counter gets large enough here:


for(i_counter=0;i_counter < arr_size;i_counter++)




For the outer loop it is when chaos variable becomes 0:


}while(chaos==1);




Thanks again,
Ilya

This post has been edited by AgentSmith: 04 June 2011 - 06:06 PM

Was This Post Helpful? 0
  • +
  • -

#8 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 06:36 PM

> while(chaos==1);

So if chaos is 1, the loop repeats. Are you sure it's not 1?
Was This Post Helpful? 1
  • +
  • -

#9 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 656
  • View blog
  • Posts: 2,247
  • Joined: 31-December 10

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 07:36 PM

You use the new operator, but there is no accompanying delete call so your program has a memory leak.
Was This Post Helpful? 1
  • +
  • -

#10 AgentSmith  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 04-June 11

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 08:29 PM

View PostOler1s, on 04 June 2011 - 06:36 PM, said:

> while(chaos==1);

So if chaos is 1, the loop repeats. Are you sure it's not 1?


I do not think it will be "1" once it is done sorting. Because every round the "for" loop sets Chaos=0, and if nothing is found to change it should remain 0.

It is strange this code doesn't work. :(
Was This Post Helpful? 0
  • +
  • -

#11 AgentSmith  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 04-June 11

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 09:22 PM

Hey guys, I finally figured it out! The problem was on lines 43 and 44:

items1[i_counter]=temp1;

items1[i_counter]=temp;

These lines were assigning the same value to different variables. :/
I have also tweaked a few lines to make the algorithm better (it wasn't rearranging completely) and here is the final code if anybody is interested.


#include <iostream>
#include <string>

using namespace std;

int main()
{
int arr_size;
cout << "Please enter how many words you would like to sort...\n";
cin >> arr_size;
string * items1 = new string [arr_size];
cout << "Please enter words to sort...\n";

int i_counter;

for (i_counter=0; i_counter <= arr_size-1; i_counter++) 
{
	cin >> items1[i_counter];
} 
for (i_counter=0; i_counter <= arr_size-1; i_counter++)
{
	cout << items1[i_counter] << "\n";
}

/* Now let us sort these words */
cout << "Here are the words in alphabetical order \n";
bool chaos; 

do
{
	chaos=0;
	for(i_counter=0;i_counter < arr_size-1;i_counter++)
	{
		string temp;
		string temp1;
		
			temp=items1[i_counter];
			temp1=items1[i_counter+1];
			
			if (temp > temp1)
			{
				items1[i_counter]=temp1; 
				items1[i_counter+1]=temp;
				chaos=1;
			}	

	}
				
}while(chaos==1);

for (i_counter=0; i_counter <= arr_size-1; i_counter++)
{
	cout << items1[i_counter] << ",";
}
delete [] items1;
return 0;
}




Was This Post Helpful? 0
  • +
  • -

#12 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Sorting words, stuck in infinite loop.

Posted 04 June 2011 - 09:24 PM

Quote

I do not think it will be "1"
I didn't ask if you think it is 1. I asked if it is 1 or not. Verify it.

EDIT: Glad to see you solved the issue. But debugging isn't guessing work. Just debug your program flow and you will spot the issue very quickly.

This post has been edited by Oler1s: 04 June 2011 - 09:25 PM

Was This Post Helpful? 0
  • +
  • -

#13 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 249
  • View blog
  • Posts: 582
  • Joined: 31-May 11

Re: Sorting words, stuck in infinite loop.

Posted 05 June 2011 - 06:27 AM

Now as an exercise see how naive bubble sort looks like and implement it. Observe how does it differ from your code. Try to optimize it (you can sort a large set of data, and time it, to see if your version is faster or not).
Then, if you want even more fun with sorting, see how other sorting algorithms work. These will probably require you to know about recursion, sometimes trees, and other useful stuff that you're bound to learn one way or another.
Implementing quicksort is fun too.

For a nice inspirational video see these: http://www.youtube.c...h?v=t8g-iYGHpEA
http://www.youtube.c...feature=related
http://www.youtube.c...dXoUgYQebM&NR=1
And you'll find others. ;)

This post has been edited by Xupicor: 05 June 2011 - 06:30 AM

Was This Post Helpful? 1
  • +
  • -

#14 AgentSmith  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 04-June 11

Re: Sorting words, stuck in infinite loop.

Posted 05 June 2011 - 08:33 AM

View PostXupicor, on 05 June 2011 - 06:27 AM, said:

Now as an exercise see how naive bubble sort looks like and implement it. Observe how does it differ from your code. Try to optimize it (you can sort a large set of data, and time it, to see if your version is faster or not).
Then, if you want even more fun with sorting, see how other sorting algorithms work. These will probably require you to know about recursion, sometimes trees, and other useful stuff that you're bound to learn one way or another.
Implementing quicksort is fun too.

For a nice inspirational video see these: http://www.youtube.c...h?v=t8g-iYGHpEA
http://www.youtube.c...feature=related
http://www.youtube.c...dXoUgYQebM&NR=1
And you'll find others. ;)


Thank you! I like this type of coding :)
Was This Post Helpful? 0
  • +
  • -

#15 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 656
  • View blog
  • Posts: 2,247
  • Joined: 31-December 10

Re: Sorting words, stuck in infinite loop.

Posted 05 June 2011 - 11:38 AM

Did no one see my post, or see how the OP's code has a memory leak in it? When you use dynamic memory allocation(using the new operator), there needs to be a delete statement somewhere to delete the memory you allocated with the new operator. If you don't, you will end up with a memory leak which is a serious issue.
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2