Thread: Sorting problem?

  1. #1
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489

    Question Sorting problem?

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct {
      int id;
      const char *data;
    } Test;
    
    int main() {
      Test **array = malloc(3 * sizeof(Test *));
    
      (*(array)) = malloc(sizeof(Test));
      (*(array))->id = 3;
      (*(array))->data = "3";
    
      (*(array + 1)) = malloc(sizeof(Test));
      (*(array + 1))->id = 2;
      (*(array + 1))->data = "2";
      
      (*(array + 2)) = malloc(sizeof(Test));
      (*(array + 2))->id = 1;
      (*(array + 2))->data = "1";
    
      int i;
      for(i=0; i<3; i++) {
        printf("%s ", (*(array + i))->data);
      }
      
      for(i=1; i<3; i++) {
        int j;
        for(j=i; j>-1; j--) {
          if(((*(array + i))->id) < ((*(array + j))->id)) {
            Test *tmp = *(array + i);
            *(array + i) = *(array + j);
            *(array + j) = tmp;
          }
        }
      }
    
      printf("\n");
    
      for(i=0; i<3; i++) {
        printf("%s ", (*(array + i))->data);
      }
    
      return 0;
    }
    Can anyone guess?
    Is there something wrong with its algorithm or code?

    The output should be: 1 2 3
    But it is: 2 1 3

    ?
    Last edited by audinue; 01-05-2009 at 05:01 PM.
    Just GET it OFF out my mind!!

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    You seem to malloc more than needed.

    First, what's wrong with:
    Code:
    Test array[3];
    If, for some reason you need to allocate the array dynamically, why not
    Code:
    Test* array = malloc( 3 * sizeof(Test) );
    The output also seems to indicate that the array is not sorted correctly. Look up bubble sort and don't try to be too clever (bubble-sort compares items that are next to each other and runs over the array (or part of it) as many times as needed.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    In your sorting loop, it looks like you're starting at element 1, not zero, so it doesn't get sorted.

    I'd recommend using this for your loops:

    Code:
    for(i = 0; i < 3 - 1; i++)  {
       for(j = i + 1; j < 3; j++)  {
          if(...
          //do all your comparisons and swaps as needed
    
       }
    }
    
    //this is selection sort (very close to a bubble sort), and guaranteed to work right
    //if your comparison and swaps are right.

  4. #4
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    Quote Originally Posted by anon View Post
    You seem to malloc more than needed.

    First, what's wrong with:
    Code:
    Test array[3];
    If, for some reason you need to allocate the array dynamically, why not
    Code:
    Test* array = malloc( 3 * sizeof(Test) );
    The output also seems to indicate that the array is not sorted correctly. Look up bubble sort and don't try to be too clever (bubble-sort compares items that are next to each other and runs over the array (or part of it) as many times as needed.
    Quote Originally Posted by Adak View Post
    In your sorting loop, it looks like you're starting at element 1, not zero, so it doesn't get sorted.

    I'd recommend using this for your loops:

    Code:
    for(i = 0; i < 3 - 1; i++)  {
       for(j = i + 1; j < 3; j++)  {
          if(...
          //do all your comparisons and swaps as needed
    
       }
    }
    
    //this is selection sort (very close to a bubble sort), and guaranteed to work right
    //if your comparison and swaps are right.
    So, the problem was its algorithm thanks Adak.

    anon: I'm practicing my pointer logic. It seems that people in sf.net love using pointers so that I can't read their source code Thanks for reply anyway.
    Just GET it OFF out my mind!!

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by audinue View Post
    Ugly C Lover
    Confirmed:
    Quote Originally Posted by audinue View Post
    Code:
      (*(array + 1)) = malloc(sizeof(Test));
    Most people prefer "array[1] = ...";
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    Quote Originally Posted by iMalc View Post
    Confirmed:

    Most people prefer "array[1] = ...";
    Yay, thats too C
    Just GET it OFF out my mind!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting (asymptotic) complexity problem
    By Petike in forum C++ Programming
    Replies: 8
    Last Post: 01-20-2009, 07:15 AM
  2. Array Sorting problem
    By ___________ in forum C++ Programming
    Replies: 4
    Last Post: 07-22-2008, 12:17 AM
  3. What is problem about the sorting?
    By Mathsniper in forum C Programming
    Replies: 2
    Last Post: 04-17-2005, 07:00 AM
  4. Sorting text file problem...
    By John-m in forum C Programming
    Replies: 3
    Last Post: 10-01-2002, 04:51 PM
  5. Sorting array output problem
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 02-19-2002, 01:44 PM