Thread: How To Make A Quick Sort For LS

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    14

    Post How To Make A Quick Sort For LS

    For an assignment at Uni, ive been writing my own version of LS. Its been going quite well, it will work with ls,ls -a, ls -l, ls-al and any of those with a directory. I would like some suggestions on how i could go about putting all the printf's i have into some kind of array so that i can run quick sort on them to order the directory and file names from a to z.

    Hope someone out there has an idea, i'm currently trying out snprintf but its very messy!

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Can I be the judge of what is and is not messy? I would love to see your current code, Chris. You typically would not sort out the output strings so much as you would sort whatever it is that you are going to output. I am thinking a merge sort may be best when considering LS could be used to list an entire root tree and all its sub-directories.

  3. #3
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Real quick, what do you mean by snprintf is messy?

    Also how are you using your printf statements...are they taking on more than one argument? Are you needing to only sort in lexicographical order of your first argument then?

    There are a number of questions raised by your problem statement. Some short snipets of your code may help in order for us here in the forums to add their input.

  4. #4
    Registered User
    Join Date
    Nov 2008
    Posts
    14
    Hi, some more info that may help you guys!

  5. #5
    Registered User
    Join Date
    Nov 2008
    Posts
    14
    The bottom of the code with the sort function, i don't want to post everything here just in case someone else on my course finds this and starts using it. If you want more info let me know

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I'm pretty sure that the real ls works like this:
    read the filename and stat, store the stat value in an array (one way to do this is to have an array of pointer to stat, and allocate a new stat pointer for each entry), and store the stat value for each directory entry.

    You can either insert the elements into the array using "insertion sort", or when you are finished, use the standard qsort() to sort the final list of all files. The latter, I'm pretty sure, is what I did when I had a similar task 15 or so years ago.

    --
    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 slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    qsort will work just fine as long as your new ls program is not to be used exclusively on very large listings.

    Though with your use of printf statements you could modify your ls program to sort on other factors and not just on the name of the file. Though that would be another specification and requirement to what you are trying to achieve but you should always think ahead of the pack, hehe.

  8. #8
    Registered User
    Join Date
    Nov 2008
    Posts
    14
    with the version of this i have posted up at the moment the compiler doesn't like these lines:

    #define AUTOLINE line[(((++linec))%2)]
    #define THISLINE line[((linec)%2)]

    get the following message:

    ls4.c: In function `main':
    ls4.c:113: warning: operation on `linec' may be undefined

    that repeats from that line until around line 200. The program does work but its that error that has started me looking for a better more efficent solution. Can you guys give me some snippets of code??

  9. #9
    Registered User
    Join Date
    Nov 2008
    Posts
    14
    line 113 is the first of my snprintfs

    snprintf(AUTOLINE,256+NAME_MAX,"%sd",THISLINE); /*directory*/

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Isn't that just an overly elaborate way of saying line[0] and line[1] ?

    Expand the statement,
    snprintf(line[(((++linec))%2)],256+NAME_MAX,"%sd",line[((linec)%2)]); /*directory*/
    Since you've no control over whether the compiler uses Red or Blue first, the operation is marked as possibly undefined.
    You don't want this if you can possibily avoid it.
    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.

  11. #11
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Salem I was thinking along the same lines but since there is an operator bound to the first instance of linec, that it may be used first, but that is up to the implementation and or compiler.

    Using postfix and prefix operations on the same variable within the same function is undefined behaviour.

  12. #12
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    One *could* check out this.

  13. #13
    Registered User
    Join Date
    Nov 2008
    Posts
    14
    Ok thanks guys, I’m beginning to understand why it’s coming up with that warning now, can someone show me an example using a different approach to achieve the same thing?? or a solution to make this version slightly more predicable??

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You could use linec+1 in the place where you have ++ now, and then do linec++ on the next line.

    --
    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. can any1 plz make this assignment
    By jean in forum C Programming
    Replies: 17
    Last Post: 05-13-2009, 09:19 PM
  2. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  3. Quick, Partiotion, and Insertion Sort
    By silicon in forum C++ Programming
    Replies: 0
    Last Post: 05-18-2005, 08:47 PM
  4. Help On A Quick Sort Program
    By nick4 in forum C++ Programming
    Replies: 11
    Last Post: 12-06-2004, 10:51 AM
  5. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM