Thread: Having trouble translating psudeo-code to real-code.

  1. #1
    Registered User
    Join Date
    Aug 2004
    Location
    San Diego, CA
    Posts
    313

    Having trouble translating psudeo-code to real-code.

    I'm trying to write a sorting algorithm for fun. The problem is that I am having a REALLY HARD TIME translating psudeo-code into real code.

    Psudeo code:

    if element_X < element_Y
    swap element_X, element_Y
    X++
    Y++
    repeat

    This is supposed to let me sort from largest to smallest. However, when I try to translate it into code, I run into problems.

    Code:
    // Includes
    
    #include <iostream>
    
    // Functions
    
    int sort(char one, char two);
    
    // Code
    
    int main(int argc, char* argv[])
    {
    	char* list = argv[1];
    	char temp;
    	int retval;
    	
    	if (argc != 2)
    	{
    		std::cout << "You input the wrong number of arguments. The correct usage is 'main <list>'.";
    		return(0);
    	}
    	
    	for (int x = 0; x < strlen(argv[1]);)
    	{
    		retval = sort(list[x], list[x+1]);
    		
    		std::cout << list[x] << list[x+1] << "\t";
    		
    		if (retval == 1 || retval == 3)
    		{
    			x++;
    		}
    		
    		if (retval == 2)
    		{
    			temp = list[x];
    			list[x] = list[x+1];
    			list[x+1] = temp;
    		}
    		
    		std::cout << list << std::endl;
    	}
    	
    	std::cout << list;
    	
    	return(0);
    }
    
    int sort(char one, char two)
    {	
    	if (one > two) return(1);
    	if (one < two) return(2);
    	if (one == two) return(3);
    	else return(0);
    }
    And here's the output of the program.. I STILL can't figure out where it's screwing up.

    01 1023456789
    10 1023456789
    02 1203456789
    20 1203456789
    03 1230456789
    30 1230456789
    04 1234056789
    40 1234056789
    05 1234506789
    50 1234506789
    06 1234560789
    60 1234560789
    07 1234567089
    70 1234567089
    08 1234567809
    80 1234567809
    09 1234567890
    90 1234567890
    0 1234567890
    1234567890
    I would be much oblidged if assistance could be given?

  2. #2
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    is the problem simply that the 0 comes after 9?...

    if so your program works fine......

    zero as a character has a higher value then nine as a character.....you have to convert argv into integers

  3. #3
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    char a = '1';
    //atoi means ascii to integer
    int i = atoi(a, 10);

    look up atoi to make sure that's right....if the last param of atoi is 'radix' just use 10...
    i can't remember if that function needs a radix or not.....

    btw, a radix just means what base numbering system to use, 10 means decimal, 8 is octal, 16 is hexidecimal...

  4. #4
    Registered User
    Join Date
    Aug 2004
    Location
    San Diego, CA
    Posts
    313
    *blink-et-y*

    Not really. Here's another example with characters.

    AB BACDEFG
    BA BACDEFG
    AC BCADEFG
    CA BCADEFG
    AD BCDAEFG
    DA BCDAEFG
    AE BCDEAFG
    EA BCDEAFG
    AF BCDEI am sillyI am sillyI am silly
    FA BCDEI am sillyI am sillyI am silly
    AG BCDEFGA
    GA BCDEFGA
    A BCDEFGA
    BCDEFGA
    The result *should* be "GFEDCBA" if I was doing it right.

  5. #5
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    sorry...i didn't really look at your code...

    i still haven't really....
    but...did that start of as ABCDEFG?.....

    if so, then you need to create another loop...after A gets to the end the program ends...
    you got to make it where you go back and do the same thing to B, and then C and so on....
    Last edited by misplaced; 10-04-2004 at 05:59 PM.

  6. #6
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    if element_X < element_Y
    swap element_X, element_Y
    X++
    Y++
    repeat
    __________________________________________
    | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

    with your algorithm i believe youhave x and y as ajacent elements so your compareing element 1 with element 2 and if element 1 < element 2 then swap elements and increment both x and y so now your compareing element 2 and element 3 so on one pass you would get the following
    1 2 3 4 5
    1<2 so swap

    2 1 3 4 5
    1<3 so swap

    2 3 1 4 5
    1<4 so swap

    2 3 4 1 5
    1<5 so swap

    so your just moving 1 up the list on the first pass
    you would have to make repeated passes until you can
    iterate through the list without having to swap.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  7. #7
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    do a search of the board for bubble sort or just sort---many of the generic sorts will turn out to be bubble sorts. Basically you use two loops, one nested in the other; the outer to control how many times you loop through the group of elements you are sorting and the inner to control which two elements of the group you are actually comparing.

  8. #8
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    I've noticed that bubble sort is really really popular. But isn't selection sort faster and just as easy to program? (I haven't studied it in depth, but this logically seems to be the case to me)
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  9. #9
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Quote Originally Posted by Hunter2
    I've noticed that bubble sort is really really popular. But isn't selection sort faster and just as easy to program? (I haven't studied it in depth, but this logically seems to be the case to me)
    both are n^2 algorithms.

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Both pretty much suck IMO.

  11. #11
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by misplaced
    zero as a character has a higher value then nine as a character.
    Wrong.
    '0' = 48
    '1' = 49
    ...
    '9' = 57
    in ascii table values

  12. #12
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by Lithorien
    Code:
    	retval = sort(list[x], list[x+1]);
    	if (retval == 1 || retval == 3)
    	{
    		x++;
    	}
    	
    	if (retval == 2)
    	{
    		temp = list[x];
    		list[x] = list[x+1];
    		list[x+1] = temp;
    	}
    /*..........*/
    
    int sort(char one, char two)
    {	
    	if (one > two) return(1);
    	if (one < two) return(2);
    	if (one == two) return(3);
    	else return(0);//this isn't necessary
    }
    According to you sort function the retval if's should be changed (if you want ascending order), and an increment added to any case.
    Code:
    	retval = sort(list[x], list[x+1]);
    	if (retval == 1){
    		temp = list[x];
    		list[x] = list[x+1];
    		list[x+1] = temp;
    	}	
    	x++;
    Second, you're only making one loop, that way ordering only one element
    Code:
    for (int x = 0; x < strlen(argv[1]);){
    /*.....*/
    }
    Sould be
    Code:
    for (int y = 0; y < strlen(argv[1]);y++){
    	for (int x = 0; x <  strlen(argv[1])-y;x++){//x< strlen(argv[1])-y for bubble sort , x<stlen(argv[1]) for stupid sort
    		retval = sort(list[x], list[x+1]);
    		if (retval == 1){
    			temp = list[x];
    			list[x] = list[x+1];
    			list[x+1] = temp;
    		}
    	}
    }
    Extra: stupid sort isn't to offend Lithorien.
    http://en.wikipedia.org/wiki/Stupid_sort

    and find a way to optimize the for loops (the ending condition)
    Last edited by xErath; 10-05-2004 at 09:36 AM.

  13. #13
    Registered User
    Join Date
    Aug 2004
    Location
    San Diego, CA
    Posts
    313
    Thank you all for the help! I took a bunch of your answers, mashed them together, and found something that worked. If you'd like to see the code, here you are:

    Code:
    // Includes
    
    #include <iostream>
    
    // Functions
    
    // Code
    
    int main(int argc, char* argv[])
    {
    	char* list = argv[1];
    	char temp;
    	
    	if (argc != 2)
    	{
    		std::cout << "You input the wrong number of arguments. The correct usage is 'main <list>'.";
    		return(0);
    	}
    	
    	for (int x = 0; x < strlen(argv[1]); x++)
    	{
    		for (int y = 0; y < strlen(argv[1]); y++)
    		{
    			if (list[y] < list[y+1])
    			{
    				temp = list[y];
    				list[y] = list[y+1];
    				list[y+1] = temp;
    			}
    			
    			std::cout << list[x] << list[x+1] << "\t";
    			std::cout << list << std::endl;
    		}
    	}
    	
    	std::cout << list;
    	
    	return(0);
    }

  14. #14
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    A last issue
    Code:
    for (int x = 0; x < strlen(argv[1]); x++){
        for (int y = 0; y < strlen(argv[1]); y++)
            /*........*/
    strlen(argv[1]); IS EVALUATED every time a cicle is run. Therefore your code like it is now, is extremely inefficient.
    Write this:
    Code:
    int len = strlen(argv[1])-1;
    for (int x = 0; x < len; x++){
        for (int y = 0; y < len; y++)
            /*........*/
    So strlen is evaluated only once.
    Why len = ... -1 ?? Note that list[y] = list[y+1];
    y+1 would refer to the string's terminating zero

    Second, I sugested optimizing internal loop
    Consider the following:
    Code:
    //input
    S W R T I K F G
    //and size
    len = strlen(argv[1]);//len = 7
    //your internal cicle
        for (int y = 0; y < strlen(argv[1]); y++)
    //after 0 iterations
    S W R T I K F G
    //after 1 iterations
    S R T I K F G W
    //after 2 iterations
    R S I K F G T W
    //after 3 iterations
    R I K F G S T W
    //after 4 iterations
    I K F G R S T W
    //after 5 iterations
    I F G K R S T W
    //after 6 iterations
    F G I K R S T W
    //after 7 iterations
    F G I K R S T W
    After N iterations the N final elements are already sorted, therefore runing the internal cicle all the way till the last element is unecessary, even worst, waste of CPU. So if N elements are sorted (N is stored in your var x) you cicle may been written like this:
    Code:
        for (int y = 0; y < len-x-1; y++)
    What I'm sugesting is a correct bubble sort algorithm, you a less eficient one.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Programming Puns
    By kermi3 in forum A Brief History of Cprogramming.com
    Replies: 44
    Last Post: 03-23-2002, 04:38 PM
  2. << !! Posting Code? Read this First !! >>
    By biosx in forum C++ Programming
    Replies: 1
    Last Post: 03-20-2002, 12:51 PM
  3. Replies: 0
    Last Post: 02-21-2002, 06:05 PM
  4. Replies: 4
    Last Post: 01-16-2002, 12:04 AM
  5. Real Men Code in Hex
    By [A7h] in forum A Brief History of Cprogramming.com
    Replies: 20
    Last Post: 01-15-2002, 11:31 PM