Thread: Sort strings in lexicographical order but no built-in string functions allowed

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    8

    Question Sort strings in lexicographical order but no built-in string functions allowed

    After many advices, helps, I could eventually solve this problem myself, happy~~

    All I did was to write a replacement function for strcmp() and then use a bubble sort function to sort input strings in lexicographical order.

    Much simpler than nasty nested loops :P

    my_strcmp():
    Code:
    int my_strcmp (char *str1, char *str2)
    {  
    	int id = 0;
    
    	char *temp1, *temp2;
    
    	temp1 = my_strlwr(str1);
    	temp2 = my_strlwr(str2);
    
    	while(!(id = *temp1 - *temp2) && *temp2)
    	{
    		++temp1, ++temp2;
    	}
    
    	if (id < 0)
    	{
    		id = -1;
    	}
    	else if (id > 0)
    	{
    		id = 1;
    	}
    
    	return id;
    }
    In fact, I got the realization from the source code algorithm. The important part is that I understand how this algorithm works now.

    Below is the original problem:
    Hi,

    I want to write a function to perform lexicographical sorting using a simple bubble sort technique. So far I've got the basic code running, but something is not right. I can tell the algorithm is wrong but cannot fix it, please help.

    Here is my function:
    Code:
    int bubble_sort(char **words, int num_word)
    {
    	int x, y, z;
    	char *temp;
    
    	for (x = 0; x < num_word; x++)
    	{
    		for (y = 0; y < (num_word-1); y++)
    		{
    			for (z = 0; z < (WORD_SIZE+1); z++)
    			{
    				if (words[y][z] < words[y+1][z])
    				{
    					temp = words[y+1];
    					words[y+1] = words[y];
    					words[y] = temp;
    					break;
    				}
    				else
    				{
    					continue;
    				}
    			}
    		}
    	}
    
    	return 0;
    }
    I've tried not to use the third inner loop, but then it will just perform the first letter comparison...And yes, let me stress that strcmp or strncmp should not be used...

    Thank you in advance.
    Last edited by woozy; 10-21-2007 at 02:45 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Write your own drop-in replacement for strcmp() so you can simplify your code.

    Or use strcmp() anyway until the sort is working, then develop your own strcmp() replacement.

    Nobody said you couldn't use the standard library to test with
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    8
    Actually the purpose of what I'm doing here is to understand the algorithm of strcmp.

    So yeah, I'd rather not use it and keep on trying (and keep on trying to ask too ;p)

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Actually the purpose of what I'm doing here is to understand the algorithm of strcmp.
    In that case, do not complicate it by integrating it into a sorting algorithm. Just write it as a function, then test with a few cases.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Oct 2007
    Posts
    8
    Then the other purpose fails - which is to sort these word strings into lexicographical order.

    But anyways, I agree with both of ya, I'll try to write a replacement for strcmp first, then later on drop it into my sorting loop.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by woozy View Post
    Then the other purpose fails - which is to sort these word strings into lexicographical order.

    But anyways, I agree with both of ya, I'll try to write a replacement for strcmp first, then later on drop it into my sorting loop.
    That's right. It is easier to implement one at a time and know that one works before trying the next. Otherwise you will be left wondering whether the bug (or bugs) lies in your string comparison, your sorting, or both.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    8
    Now I've done a replacement for strcmp(), and also I found the source code of strcmp() in the standard lib...

    I wonder which one is more efficient

    mine:
    Code:
    int my_strcmp(char *str1, char *str2)  
    {  
    	char* p1;
    	char* p2;
    	
    	p1 = str1;
    	p2 = str2;
    
    	while (*p1 && *p2)
    	{
    		if (*p1 == *p2)
    		{
    			p1++;
    			p2++;
    		}
    		else
    		{
    			return (*p1 - *p2);
    		}
    	}
    	
    	return (*p1 - *p2);
    }
    strcmp() source rewritten:
    Code:
    int my_strcmp (char *str1, char *str2)
    {  
    	int id = 0;  
    
    	while(!(id = *str1 - *str2) && *str2)
    	{
    		++str1,   ++str2;
    	}
    
    	if (id < 0)
    	{
    		id   =   -1;
    	}
    	else if (id > 0)
    	{
    		id = 1;
    	}
    
    	return id;
    }

  8. #8
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    It probably doesn't matter. You can't compare two character strings for equality without taking into account that the only place two strings might differ is at the end. Therefore, even aggressively optimized comparisons are linear time.

  9. #9
    Registered User
    Join Date
    Oct 2007
    Posts
    8
    Hi citizen,

    Thank you for your advice. I'm not yet trying to optimize anything, but to implement some algorithm.


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ ini file reader problems
    By guitarist809 in forum C++ Programming
    Replies: 7
    Last Post: 09-04-2008, 06:02 AM
  2. Inheritance Hierarchy for a Package class
    By twickre in forum C++ Programming
    Replies: 7
    Last Post: 12-08-2007, 04:13 PM
  3. String Class
    By BKurosawa in forum C++ Programming
    Replies: 117
    Last Post: 08-09-2007, 01:02 AM
  4. String issues
    By The_professor in forum C++ Programming
    Replies: 7
    Last Post: 06-12-2007, 09:11 AM