Thread: c - line sorting program

  1. #1
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272

    c - line sorting program

    This program sorts lines in input alphabetically/numerically depending on the arguments passed to main.

    So i came accros this exercise in k&R:

    Add a field-handling capability, so sorting may be done on fields within lines, each field sorted according to an independent set of options. (The index for this book was sorted with -df for the index category and -n for the page numbers.)

    I suppose field is a string of characters in between blanks, is that correct?

    The way i tought i should handle this is, let the user enter max 2 numbers in arguments: first for the starting field, second for the ending field, and then perform comparison of all the lines between those fields, and ofcourse work properly with flags aswell

    Is this about~ what the authors had in their minds?

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Not sure what you mean by "starting" and "ending" field. I would take the example (of the index) to mean that there is primary and secondary sorting criteria. The data is sorted alphabetically by the primary criteria, then ties are resolved using the secondary criteria, eg:

    alpha 10
    beta 5
    beta 7
    beta 300
    gamma 12
    gamma 14

    You could do the same thing with a list of names, where the primary is the last name and the secondary the first name. So there are two distinct issues: the field selection, and the sorting method (alphabetical, numeric, ascending, descending).
    Last edited by MK27; 01-13-2010 at 01:33 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    -sort -2 -5

    Sorts lines by comparing fields 2 to 5 in line, and field being for example:
    ab asd asq poa
    ab is first field, asd second field etc.

    This?

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    What if you wanted to sort by the 2nd field, then the 5th field?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    A field is one part of a record. Say you are a student, in a database. You'd have a field for first name, another field for last name, another field for your student ID number, etc. Structs and their members are designed to handle (be), records and their fields.

    Fields can be whatever you want them to be, as long as they are the same type of data.

    MK27, the second field isn't to resolve ties, it has it's own sorting sub-action to be done. The index of a book is a good example. Sorted alphabetically by subject, and then by page number as the secondary key.
    Last edited by Adak; 01-13-2010 at 01:46 PM.

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Adak View Post
    MK27, the second field isn't to resolve ties, it has it's own sorting sub-action to be done. The index of a book is a good example. Sorted alphabetically by subject, and then by page number as the secondary key.
    Dude, that IS RESOLVING A TIE. How do all the words that are the same get put together? Because they tie. Look at the index again, this time formatted a bit differently.

    alpha 10
    beta 5, 7, 300
    gamma 12, 14

    The point is, you sort first by one field, and IF there is a tie, you then sort by another criteria. Or: you could sort twice to create two different lists, one sorted by (eg), first name, the other by last name. There really are no other possibilities here. If there is only one "alpha", in what sense would you apply the other criteria?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    My program by default sorts lines alphabetically.

    If i enter sort -n, it will sort them numerically instead.

    MK, can u explain a bit more what do you suggest?

    Do you mean that i should store arguments in an array, and then iterate through the array, and if for example i enter sort -5 -n, that will sort the 5th field numerically in all the lines?

    And if i enter sort -5 -8, that will sort the lines alphabetically first in the fifth column, stdout it, and then sort it again at 8th field, and then stdout it.

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Tool View Post
    Do you mean that i should store arguments in an array, and then iterate through the array, and if for example i enter sort -5 -n, that will sort the 5th field numerically in all the lines?

    And if i enter sort -5 -8, that will sort the lines alphabetically first in the fifth column, stdout it, and then sort it again at 8th field, and then stdout it.
    Something like that. I would use getopt() for the arguments. But I don't see the purpose in producing two lists -- they will be the same as if you just ran the program twice. The way I have done this before is to call the secondary sort when two items tie, since no matter what kind of sort you use, it always comes down to comparing one item with one other item. You have three possibilities: <, >, and =.

    If the switches were, eg, -5 -n -3 -a, and item X == item Y sorted numerically by 5th field THEN you sort those two items by 3rd field alphabetically. If that's a tie too (eg, "bob 12" and "bob 12") you just leave them together, which is what you would do with a tie in a single criteria sort. But "bab 12" will beat "bob 12".

    Pretty sure this is the only logical approach here. Here's a big hint: you may want to use function pointers in your sort function parameters, like qsort does. This way you can write separate functions:

    func 1: compare one item to another alphabetically
    func 2: compare one item to another numerically
    func 3: the sorting function (bubblesort, mergesort, something you make up, or whatever).

    In fact, these are often distinguished with the terms "sort function" and "compare function". I guess you don't have to use a function pointer, but you will need a parameter to indicate the type of comparison, eg:

    mysortfunc(char *list, int length, int field, int comparison_type);

    A version with function pointers would be:
    mysortfunc(char *list, int length, int field, int (*comp_func)(void *a, void *b));

    This is a little easier and better than writing two totally separate functions, one that sorts alphabetically and one that sorts numerically, since that will get ugly when it comes time to apply the secondary criteria. This way, when the comp function returns a tie, you can just send the same two items to a different comp function.
    Last edited by MK27; 01-13-2010 at 02:28 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #9
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    Yes, im using function pointers.

    This is the function that gets called in qsort in main:

    Code:
    int compare(char *s1, char *s2)
    {
    	int i, d;
    	char *f1, *f2;
    
    	for (i = 0; i < num_fields; i++) {
    		f1 = field_of(s1, fieldarray[i]);
    		f2 = field_of(s2, fieldarray[i]);
    		d = compare_field(f1, f2, flagarray[i]);
    		
    		if(d != 0)
    		   return d;
    	}
    	if (numeric)
    		d = numcmp(s1, s2);
    	else if (directory)
    		d = dircmp(s1, s2);
    	else
    		d = stringcmp(s1, s2);
    
    	if (reverse)
    		return -d;
    	else
    		return d;
    }
    The *field_of function returns a buffer which contains the field to compare_fields which then returns a value to int d, and if d is 0(equal) it continues to for loop the arguments.

    Is this something you had in mind?

    Also, it works with options like reverse and directory(if it compares only blanks/numbers).

  10. #10
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Tool View Post
    Yes, im using function pointers.

    This is the function that gets called in qsort in main:

    Is this something you had in mind?
    You may have to write your own sort, because limitations in the form of the qsort compare function will make it difficult to resolve a tie by evaluating a different field. The only way I see out of that is to set some global variables indicating which fields to use,* since you can then access that in the compare function. Probably worthwhile unless you want to write your own sort (which is a pretty good exercise for learning how to implement an algorithm, sorts vary from very simple to pretty complex IMO).

    *actually looking at your code it seems you are already doing all this...
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  2. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 11:17 PM
  3. How use a Web Interface with a C command line program
    By vmehta211 in forum C Programming
    Replies: 3
    Last Post: 01-18-2006, 12:19 PM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  5. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM