Thread: Sorting question -- One pass algo

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    4

    Sorting question -- One pass algo

    Given n sorted lists of integers as file input, write a one-pass algorithm that produces one sorted file of output, where the output is the sorted merger of the n input files.

    I was thinking of using Merge sort , but its complexity is O(nlogn).
    What do you guys suggest?
    How can I apply one-pass algo on n sorted list of integers??
    Suggest some strategy that will give me a kick to start.

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    1) You check the (i)th element of each list, and input them to the new list in the desired order
    2) Do step (1) untill all lists run out of elements
    Devoted my life to programming...

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Gseries
    I was thinking of using Merge sort , but its complexity is O(nlogn).
    What do you guys suggest?
    How can I apply one-pass algo on n sorted list of integers??
    You don't need merge sort as you are just merging
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Sep 2011
    Posts
    4
    @GReaper -thnx 4 replyin

    hhmm... I understand there are lot of lists.
    Say List 1, list 2, list 3, list 4....
    Each list is having different no. of elements inside it.

    say list 1 has 50, list 2 has 25 , list 3 has 100 , so on...

    I didn't get you when u said check for (i th) element?
    what does i th means??

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Gseries
    I didn't get you when u said check for (i th) element?
    what does i th means??
    Well, think of how the merge operation used in merge sort works. Now, suppose that the list (e.g., an array) has an odd number of elements. Clearly, the two partitions of the list will then be of different sizes. Does the merge still work? Why?

    Basically, the whole idea behind this is to extend this same merge operation to work on n lists.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Quote Originally Posted by Gseries View Post
    I didn't get you when u said check for (i th) element?
    what does i th means??
    Like 1st, 2nd, 3rd, 4th ... (i)th
    Devoted my life to programming...

  7. #7
    Registered User
    Join Date
    Sep 2011
    Posts
    4
    Quote Originally Posted by GReaper View Post
    Like 1st, 2nd, 3rd, 4th ... (i)th
    checking the i th element of all the lists won't make it one-pass .
    One pass would be somewhat visiting the element only once.

  8. #8
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    Depends on what you are talking about. Let's say you have 3 lists:x, y, z. You basically do:
    Code:
    for each element in x y z
         compare x[i], y[j], z[k]
         put smallest element in output list //lets say y[j]
         increment index of element added //in this case j
    repeat
    Each element is only visited once with this basic merge. Note: Your initial assumption was that each list was already sorted.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  9. #9
    Registered User
    Join Date
    Sep 2011
    Posts
    4
    Quote Originally Posted by laserlight View Post
    Well, think of how the merge operation used in merge sort works. Now, suppose that the list (e.g., an array) has an odd number of elements. Clearly, the two partitions of the list will then be of different sizes. Does the merge still work? Why?

    Basically, the whole idea behind this is to extend this same merge operation to work on n lists.
    Thanks . I understand Merge sort.
    My main issue that is coming is how can i combine the elements by only visiting them once.

  10. #10
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Quote Originally Posted by Gseries View Post
    checking the i th element of all the lists won't make it one-pass .
    One pass would be somewhat visiting the element only once.
    I meant compare the (i)th elements of the lists, each element will be visited only one.

    EDIT: Think of it this way
    Code:
    for (int i = 0; i < size; i++){
        mergedArray[i*4] = array1[i];
        mergedArray[i*4+1] = array2[i];
        mergedArray[i*4+2] = array3[i];
        mergedArray[i*4+3] = array4[i];
    
        sort(mergedArray+i*4, 4);
    }
    Or something like that...
    Last edited by GReaper; 09-28-2011 at 11:29 AM.
    Devoted my life to programming...

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Use a priority queue (heap) of lists where each item contains both the file pointer and the next unprocessed item from the file (for ordering).
    Then merge!
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pass by reference question..
    By Markusob in forum C# Programming
    Replies: 2
    Last Post: 05-09-2011, 03:26 PM
  2. sorting algo causing seg fault
    By coder123321 in forum C++ Programming
    Replies: 3
    Last Post: 11-18-2010, 01:36 PM
  3. Const pass by reference question....
    By darren78 in forum C++ Programming
    Replies: 4
    Last Post: 06-18-2010, 05:04 AM
  4. pass by reference question
    By gp364481 in forum C Programming
    Replies: 6
    Last Post: 09-11-2008, 07:00 PM
  5. pass by reference question
    By Thantos in forum C Programming
    Replies: 6
    Last Post: 11-30-2003, 04:04 PM