Sorting question -- One pass algo

Question

2.00/5 (5 votes)

See more:

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.

Posted 28-Sep-11 6:36am

Gseries

Updated 28-Sep-11 6:45am

Simon Bang Terkildsen

v2

Add a Solution

Comments

Ed Nutting 28-Sep-11 12:37pm

We don't do your H/W here. It's homework for a reason...

Sergey Chepurin 28-Sep-11 14:53pm

Problems solvable and not solvable by one-pass: http://en.wikipedia.org/wiki/One-pass_algorithm

TorstenH. 29-Sep-11 1:20am

right - nice homework.
Let's start with a brief thing: Have you already implemented the filereader and filewriter?

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Nagy Vilmos · Answer 1 · 2011-09-29T01:05:00

Solution 2

"Given n sorted lists of integers as file input"

To me this means that the inputs are sorted, so it's a case of optimising the output. Somewhere along this line will do the dirty:

for each file
  read the first number into a sorted list
end loop
while the list is non empty and the files have more items
  write the first item in the sorted list to the output
  if the item's file has more
    read next item from file into sorted list
  end if
end loop

You simply need to record which file each item comes from and have a sorted list that the items can be added into.
I will leave the implementation as an exercise for OP.

Posted 29-Sep-11 1:05am

Nagy Vilmos

Comments

Sergey Chepurin 29-Sep-11 7:37am

You wrote: "Given n sorted lists of integers as file input"
To me this means that the inputs are sorted"
----------------------------------------------------
To me this produces an unsorted list of sorted lists of integers and you have to sort it somehow.

Nagy Vilmos 29-Sep-11 7:47am

No. I think it's each of the inputs is sorted, so the problem is to merge n lists that are in themselves in order.
If we play the 'memory no object game' we could do it by reading them all into a sorted array and then write out the array, but I think that may be taken as two passes. If the inputs are not sorted then there is, AFAIK, no single pass algorithm as you'd need to read all the data before being able to completely sort it.

Sergey Chepurin 29-Sep-11 8:16am

To me, to output in some "sorted" order merged lists of sorted integers makes no sense. To sort these list makes much more sense producing the sorted output. But this has no "one-pass" solution for sure.

Nagy Vilmos 29-Sep-11 8:27am

If you take two sorted lists:
1, 2, 5 ,8, 10
3, 4, 6, 7, 9
Merge them in sorted order produces what?

AFAIK that is the point of the question.

Sergey Chepurin 29-Sep-11 9:24am

I simply consider "merging the contents of sorted lists in sorted order" = sorting the output. No one-pass solution.

Stefan_Lang 29-Sep-11 11:26am

Sorry, failed to understand the solution the first time I read it - it only came to me after writing down my own :D

Anyway my 5, for being the first with a correct solution if nothing else. ;)

Mehdi Gholam · Answer 2 · 2011-09-28T06:47:00

Solution 1

Take a look at this article here TimSort

Posted 28-Sep-11 6:47am

Mehdi Gholam

Comments

Nagy Vilmos 29-Sep-11 7:09am

TimSort requires two runs.

Chuck O'Toole 29-Sep-11 10:53am

Interesting that TimSort's desciption says that it relied on the fact that most data is "partially ordered" to begin with. Not the case here, the incoming data is in 3 lists, each properly ordered. This seems like a simple merge (not merge sort). At most, you make one pass over all 3 lists simultaneously, using the maximum number of elements on any the arrays as the limit on the loop.

Stefan_Lang · Answer 3 · 2011-09-29T05:12:00

1. Initialize the algorithm like that:

C++

read the first number from each file
sort the files by those numbers, lowest first

2. The main algorithm should work like this:

C++

while (file list not empty)
{
  do
  {
    store the number from the first file
    get the next number from that file
    if (end of file)
    {
      remove file from list
    }
  } while (most recent number <= last number read from the second file)
       or (file list not empty)

  if (file list not empty)
  {
    sort files by last read number (you only need to reposition the first file)
  }
}

P.S.: removed accidental copy of this solution

Sorting question -- One pass algo

3 solutions

Solution 2

Solution 1

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us