Thread: Complicated riddle?

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

    Complicated riddle?

    I've been in different programming forums and in on of 'em, there's a riddle that says:
    To write an algorithm that sorts an array of integers.
    What do I mean?
    For example,
    I have this array:
    Code:
    int num[8] = "{7, 5, 2, 1, 3, 4, 6, 0};
    Now, I gotta create a function that sorts the array from:
    7, 5, 2, 1, 3, 4, 6, 0
    to:
    0, 1, 2, 3, 4, 5, 6, 7

    I tried many many ways but non of my tries worked.

    How do I do it?
    Thanks.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    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
    242
    I tried to use WIkipedia, but it didn't help me.
    I tried to cast this:
    Code:
    procedure bubbleSort( A : list of sortable items ) defined as:
      for each i in 1 to length(A) do:
         for each j in length(A) downto i + 1 do:
           if A[ j -1  ] > A[ j ] then
             swap( A[ j - 1],  A[ j ] )
           end if
         end for
      end for
    end procedure
    To C, with no luck.
    How do I do it then?

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    What did you actually write? Show us the code...

    I'm pretty sure the algorithm for bubble-sort is correct, so you obviously had problems translating the pseudo-code into C.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    #include <stdio.h>
    Quote Originally Posted by matsp View Post
    What did you actually write? Show us the code...

    I'm pretty sure the algorithm for bubble-sort is correct, so you obviously had problems translating the pseudo-code into C.

    --
    Mats
    Code:
    void swap(int *a, int *b)
    {
    int temp = *a;
    *a = *b;
    *b = temp;
    }
    
    void bubbleSort(int num[])
    {
    for(int i = 0;; i < strlen(num); i++) // I know these lines aren't correct. (lol)
    for(int j = 0; strlen(num); i++) // I know these lines aren't correct. (lol)
    if(a[j-1] > a[j])
    swap(a[j-1], a[j])
    }
    
    int main(void)
    {
    int num[8] = {7, 0, 2, 3, 5, 6, 1, 4};
    for(int i = 0; i < = 7; i++)
    printf("&#37;d\n", num[i]);
    
    getchar();
    return 0;
    }

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    strlen doesn't work for non-strings. You have an array of integers, not a string. You should probably pass the number of elements in your array from the calling function (main in this case).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    It doesn't work if I replace strlen(num) with 8..
    my code:
    Code:
    #include <stdio.h>
    
    void swap(int *a, int *b)
    {
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    void bubbleSort(int num[])
    {
    	for(int i = 0; i < 8; i++)
    		for(int j = 0; 8; i++)
    			if(num[j-1] > num[j])
    				swap(&num[j-1], &num[j])
    }
    
    int main(void)
    {
    	int num[8] = {7, 0, 2, 3, 5, 6, 1, 4};
    	bubbleSort(num);
    	
    	for(int k = 0; k < = 7; k++)
    		printf("&#37;d\n", num[k]);
    
    	getchar();
    	return 0;
    }

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Explain a bit more "doesn't work", does it compile, it doesn't run, it runs but doesn't give you the right sorted result, or what?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    This is what your pseudo code said:
    for each j in length(A) downto i + 1

    Now what could this possibly mean? Obviously the "drop things in when we know what they are" strategy isn't working. Rather, the pseudo code is trying to outline the steps for sorting a list of items this way. In other words, you're doing to have to look at every item j down to item i + 1 in order to do it. You're close now just by reading the pseudo code. That is the reason programmers will use things like pseudo code, so they can think before they code a solution to a problem they may or may not understand.

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Not to mention that this line is not a "correct" for-loop:
    Code:
    for(int j = 0; 8; i++)
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    matsp, it just shows error, something about c99.
    noob.c:12: error: ‘for’ loop initial declaration used outside C99 mode
    for all for loops.

    And I know this is a not for loop, I gotta add j < 8 and to change it to j++.
    I'm kinda hurry, that's why.

    citizen, I didn't understand what you're trying to say, sorry.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by eXeCuTeR View Post
    matsp, it just shows error, something about c99.
    noob.c:12: error: ‘for’ loop initial declaration used outside C99 mode
    for all for loops.

    citizen, I didn't understand what you're trying to say, sorry.
    That is because you are using C99/C++ style "for(int j = .." instead of declaring j at the top of the function like C89 and predecessors require. But your loop is also broken in several other ways. Read through it. An important part of being a programmer is the ability to read and understand what the code you've written [or somone else] does - and why it doesn't do what you want, when it's not doing that. Look at it CAREFULLY.

    Citizen is trying to say that
    Code:
    for each j in length(A) downto i + 1
    may not be a simple for loop from 0 .. 7, perhaps?
    Read that pseudo-code and try to figure out what it means...

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    what is this downto thing?


    btw,
    I know how for loops works, it just that I'm really really hurry and stuff so I type with many errors.
    Don't mind it.

  14. #14
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    up to means count up, say from 0 to 10
    downto means count down, say from 10 to 0
    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.

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by eXeCuTeR View Post
    what is this downto thing?


    btw,
    I know how for loops works, it just that I'm really really hurry and stuff so I type with many errors.
    Don't mind it.
    Less haste, more speed, or whatever the saying is... ;-)

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Vtables riddle.
    By eXeCuTeR in forum C++ Programming
    Replies: 10
    Last Post: 07-22-2008, 01:57 PM
  2. Complicated member objects that depend on `this`
    By drrngrvy in forum C++ Programming
    Replies: 3
    Last Post: 11-12-2006, 09:48 PM
  3. The Most Complicated program
    By Prodigy in forum C++ Programming
    Replies: 5
    Last Post: 05-04-2002, 05:17 PM
  4. Pointer Riddle that is bugging me
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 09-29-2001, 11:11 PM
  5. Another riddle tread!
    By minime6696 in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-24-2001, 06:37 AM