Question about lexographically sorting values

This is a discussion on Question about lexographically sorting values within the C Programming forums, part of the General Programming Boards category; My code is supposed to take an array of user inputed values (array) and the total number of actual values ...

  1. #1
    Registered User
    Join Date
    Jul 2011
    Posts
    5

    Question about lexographically sorting values

    My code is supposed to take an array of user inputed values (array) and the total number of actual values in that array (vals) and sort the array lexicographically, that is ordering the values by relative digits. Strings cannot be used in this program

    for example, the array 9 71 174 578 1 23 should be sorted to become 1 174 23 578 71 9

    and 1 1000 1001 100000 should be 1 1000 100000 1001

    My idea was to first count the number of digits in the value at 'place' (the left most point of the unsorted part of the array], then count the digits in the value at 'c2' (value that travels down the unsorted part of the array). the actual sorting divides both of these values by 10^(number of digits - 1) which should allow the program to compare the left most digit, exchange the vale of place with c2 if the c2 digit is smaller, disregard the c2 value if its digit is greater or element c2 is the same as element place, and if multiple digits in the two values are the same it goes into a loop reducing the relative counters and doing the same comparison (so now 2 digits in both elements would be compared) until a smaller value lexicographically is found.

    Any help on this problem would be greatly appreciated

    my code is
    Code:
    void selectionSort (int array[], int vals)
    {
      //Declarations
      int c1;     //counter
      int c2;     //counter
      int c3;     //counter
      int c4;     //counter
      int c5;     //counter
      //int c6;
      int temp;     //temporary data holder
      int temp2;     //temporary data holder
      int temp3;     //used
      //int temp4;
      int end;
      int place;     //position in the array being examined
    
      //Statements
      //outer loop
      for (c1 = 0; c1 < vals; c1++)
      {
        place = c1;
        temp3 = array[place];
        c5 = 0;
        //determines number of digits in the value at element [place]
        while (temp3 != 0)
        {
          temp3 /= 10;
          ++c5;
        }
        //inner loop
        for (c2 = c1 + 1; c2 < vals; c2++)
        {
          temp2 = array[c2];
          c4 = 0;
          //determines number of digits in the value at element [c2]
          while (temp2 != 0)
          {
            temp2 /= 10;
            ++c4;
          }
          if ( (array[c2] / ( (int) pow (10, c4-1)) ) < (array[place] / ( (int) pow (10, c5-1)) ) )
          {
            place = c2;
          }
          else if ( (array[c2] / ( (int) pow(10, c4-1)) ) == (array[place] / ( (int) pow (10, c5-1)) ) )
          {
            if (array[c2] != array[place])
            {
              end = 0;
              while (end == 0)
              {
                --c5;
                --c4;
                if (c4 == 0)
                {
                  place = c2;
                  end = 1;
                }
                else if (c5 == 0)
                {
                  end = 1;
                }
                else if ( (array[c2] / ( (int) pow (10, c4-1)) ) < (array[place] / ( (int) pow (10, c5-1)) ) )
                {
                  place = c2;
                  end = 1;
                }
              }
            }
          }
        }
        //selected unsorted value placed at the end of already sorted values
        temp = array[c1];
        array[c1] = array[place];
        array[place] = temp;
        //prints the step in the sorting process
        printf("Array after pass #%d: ", c1 + 1);
        for (c3 = 0; c3 < vals; c3++)
        {
          printf("%d ", array[c3]);
        }
        printf("\n");
      }
    
      return;
    }
    the code correctly sorts when all of the values are one digit, but doesn't seem to work when values with different numbers of digits are used.
    Last edited by kuzadaman; 08-01-2011 at 05:20 PM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    sprintf + strcmp


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Jul 2011
    Posts
    5
    Sorry, I forgot to add that strings are not allowed in solving this problem

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Write a function that compares two numbers to determine what one is bigger, returning -1, 0, or 1 the way strcmp does. Use it to tell you if you should swap or not.
    Code:
    int leftmostdigit( int number )
    {
        ...
    }
    
    int numcmp( int n1, int n2 )
    {
        while digits in both numbers
            ln1 = leftmostdigit n1
            ln2 = leftmostdigit n2
            if ln1 < ln2
                return -1
            if ln2 < ln1
                return 1
            ... otherwise strip off the left most digit of both
        if digits in n1
            return 1
        if digits in n2
            return -1
        return 0
    }
    That looks about right.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting question
    By time4f5 in forum C Programming
    Replies: 3
    Last Post: 04-11-2011, 11:23 PM
  2. sorting question
    By archriku in forum C Programming
    Replies: 47
    Last Post: 03-26-2009, 01:28 PM
  3. sorting question
    By panfilero in forum C Programming
    Replies: 5
    Last Post: 11-22-2005, 08:16 AM
  4. A question about sorting..
    By NightWalker in forum C Programming
    Replies: 2
    Last Post: 11-12-2003, 09:24 AM
  5. Replies: 2
    Last Post: 03-07-2002, 09:14 AM

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