merging

This is a discussion on merging within the C++ Programming forums, part of the General Programming Boards category; Say i have n vectors that are sorted. I can't think of a better algorithm to merge than searching the ...

  1. #1
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926

    merging

    Say i have n vectors that are sorted. I can't think of a better algorithm to merge than searching the first of all n vectors to find minimum then pop that then continue. I think this would be too slow, but I can't think of anything more efficient.
    Thanks
    Michael

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I think this would be too slow
    Why? Have you tried it, profiled the execution, and determined it to be too slow? Or are you just thinking about it and going "golly, this has a lot of steps"? There are two problems with the latter:

    1) Programmers are notoriously bad at guessing where bottlenecks lie.
    2) Algorithms are notoriously good at looking slow but being zippy.
    My best code is written with the delete key.

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    You could just do a sort by taking each element of every vector at a time in no particular order. This is probably what I'd do if the vectors weren't sorted. But since they are, your idea sounds pretty good.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    When you have more than 2 sorted vectors to merge, an excellent way to handle the merging is to reference each vector in a heap. Whether that means that your heap stores pointers to the vectors, or indexes to those vectors within the array of those vectors is up to you.
    You always extract an item from the vector that is at the head of the heap. Then you downheap (or is it upheap, I get mixed up), and repeat

    That's the way to do external mergesort.
    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"

  5. #5
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    I like the heap idea. I get upheap and downheap confused too don't worry lol. but I'm not sure if I shouldn't just take Prelude's advice. Eh I'll code both. Thanks for the advice. I greatly appreciate it!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. File I/O merging and adding
    By stevedawg85 in forum C++ Programming
    Replies: 4
    Last Post: 05-06-2006, 09:21 AM
  2. merging dll with .exe
    By johny145 in forum Windows Programming
    Replies: 8
    Last Post: 10-11-2005, 05:09 PM
  3. Help With Merging Sorted Lists of Strings
    By genjiguy in forum C++ Programming
    Replies: 3
    Last Post: 04-14-2005, 03:53 PM
  4. Merging two lists as one
    By Lone in forum C++ Programming
    Replies: 1
    Last Post: 03-17-2005, 02:59 PM
  5. Merging Linked Lists
    By Unregistered in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2001, 07:08 PM

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