A bit of explanation needed.

This is a discussion on A bit of explanation needed. within the C Programming forums, part of the General Programming Boards category; Ok, so I have this program that sorts n number of integers in an array. If the integer is below ...

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    46

    Question A bit of explanation needed.

    Ok, so I have this program that sorts n number of integers in an array. If the integer is below Threshold it sorts them in ascending order and if the integer is equal to or larger than Threshold they are sorted in descending order.

    I'm using the qsort function to do this, first to sort all of the integers in ascending order and then afterwards sorting them again with the threshold taken into account.

    Now the actual question is, how come that if I call srand before filling my array with 'random' numbers its sorted in the way I want it, but if I don't, I just get some random sort.

    PS: Obviously this is just an example code, but it displays what it is that I'm trying to do, and I don't know why this is working the way it is/isn't... and I'm somewhat new at programming in C.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define THRESHOLD 10
    
    int CompareIntsAsc(const void* a, const void* b)
    {
        int* val1 = (int*) a;
        int* val2 = (int*) b;
        
        if( *val1 < *val2 )
        {
            return -1;
        }
        else if ( *val1 == *val2 )
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
    
    int CompareIntsThreshold(const void* a, const void* b)
    {
        int* val1 = (int*) a;
        int* val2 = (int*) b;
        
        if( *val1 < THRESHOLD )
        {
            if( *val1 < *val2 )
            {
                 return -1;
            }
            else if ( *val1 == *val2 )
            {
                 return 0;
            }
            else
            {
                return 1;
            }
        }
        else
        {
            if( *val1 < *val2 )
            {
                 return 1;
            }
            else if ( *val1 == *val2 )
            {
                 return 0;
            }
            else
            {
                return -1;
            }
        }
    }
    
    int main()
    {
        int Size = 20, Data[Size], i = 0;
        int Range = Size;
        
        srand(12);
        
        for( i = 0; i < Size; i++ )
        {
             Data[i] = rand() % Range;
        }
        
        qsort(Data,Size,sizeof(int),CompareIntsAsc);
        qsort(Data,Size,sizeof(int),CompareIntsThreshold);
        
        for( i = 0; i < Size; i++ )
        {
             printf("%i\n",Data[i]);
        }
        
        getchar();
    }

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,451
    > Now the actual question is, how come that if I call srand before filling my array
    > with 'random' numbers its sorted in the way I want it, but if I don't, I just get some random sort.
    Luck probably.

    As it stands, you can remove the first call to qsort() because it has no effect on what the second call to qsort() will ultimately return. If you have some complex 'rule', then it all needs to be encoded into the single compare function for a single call to qsort.

    > if( *val1 < THRESHOLD )
    You're also (apparently) assuming that the first pointer passed to the function is always at the lower address, and this isn't guaranteed at all.
    You need 3 cases
    - both below threshold
    - either below threshold
    - neither below threshold

    I don't think your second function can ever provide a stable answer, and qsort just bumbles along until it thinks the job is done.
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Banned
    Join Date
    May 2007
    Location
    Berkeley, CA
    Posts
    329
    Couldn't you simplify the following code down to something like the following

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define THRESHOLD 10
    
    int CompareIntsAsc(const void* a, const void* b)
    {
      int* val1 = (int*) a;
      int* val2 = (int*) b;
        
      if( *val1 < *val2 )
        {
          return -1;
        }
      else if ( *val1 == *val2 )
        {
          return 0;
        }
      else
        {
          return 1;
        }
    }
    
    int main(void)
    {
      int Size = 20, Data[Size], i = 0;
      int Range = Size;
      int j;    
    
      srand(12);
        
      for( i = 0; i < Size; i++ )
        {
          Data[i] = rand() % Range;
        }
        
      qsort(Data,Size,sizeof(int),CompareIntsAsc);
      /*(qsort(Data,Size,sizeof(int),CompareIntsThreshold);*/
        
      /*Yes i know this loop sucks monkeys butt*/
      for(i = 0; Data[i] < THRESHOLD; Data[i++])
        printf("%i\n",Data[i]);
      for(i = Size-1; Data[i]  >= THRESHOLD; Data[i--])
        printf("%i\n",Data[i]);
            
      /*getchar();*/
      return 0;
    }
    Also, I don't think it would matter if the sort was stable in this case. I could be wrong, but I think the only time you would need a stable sort is if you were sorting something like the following

    Beer, beer, Booze, booze

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,638
    Stable sorting simply means that the comparison function only considers a part of the whole data so it maintains the state of the data as much as possible. This can be a problem if you expect the other parts to maintain a certain order, like 2:1 2:0 1:0 3:-1. Also, items that compare equal are considered to be sorted and not relocated. In this case it doesn't matter.

    It also shouldn't be hard to write a function for qsort now that Salem has outlined the cases. I got one working, but it looks like this:

    Before sort:
    6, 18, 2, 8, 14, 17, 7, 15, 0, 2, 5, 14, 5, 10, 12, 1, 19, 13, 4, 17,
    After sort:
    10, 12, 13, 14, 14, 15, 17, 17, 18, 19, 8, 7, 6, 5, 5, 4, 2, 2, 1, 0,

    I consider this as acceptable. It meets the requirements after all.
    Last edited by whiteflags; 11-24-2007 at 04:43 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 16 bit compilar or 32 bit compilar
    By rajkumarmadhani in forum C Programming
    Replies: 16
    Last Post: 12-04-2007, 08:48 AM
  2. strswap. Explanation needed.
    By kantze in forum C Programming
    Replies: 5
    Last Post: 10-21-2006, 10:53 AM
  3. Need a bit explanation!!
    By cBegginer in forum C Programming
    Replies: 4
    Last Post: 04-17-2005, 01:36 AM
  4. Explanation needed, what is this?
    By CAP in forum C Programming
    Replies: 8
    Last Post: 06-25-2002, 04:07 AM
  5. strcpy syntax explanation needed
    By blight2c in forum C++ Programming
    Replies: 3
    Last Post: 03-16-2002, 07:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21