Click here to Skip to main content
15,867,594 members
Please Sign up or sign in to vote.
4.60/5 (3 votes)
See more:
This is regarding the solution of the following problem "Fuzzy Sorting of Intervals" from the book "Introduction to Algorithm"
I have found a few solutions on the internet. But have a doubt.
In all the given solutions, we are only splitting the Left partition into "Left" and "Middle" so that "Middle" overlaps with pivot element and need not be sorted.
Why do we not also split the "Right" into "Middle" and "Right" so that "Middle" overlaps with pivot and need not be sorted.

Problem
Consider a sorting problem in which the numbers are not known exactly. Instead, for each number, we know an interval on the real line to which it belongs. That is, we are given n closed intervals of the form [ai, bi], where ai ≤ bi. The goal is to fuzzy-sort these intervals, i.e., produce a permutation 〈i1, i2,..., in〉 of the intervals such that there exist cj in each [aj,bj] , satisfying c1 ≤ c2 ≤ ··· ≤ cn.

Solutions on the internet
courses.csail.mit.edu/6.046/spring04/handouts/ps2-sol.pdf
web.media.mit.edu/~dlanman/courses/cs157/HW3.pdf


Note to Moderator
I apologize if this question is not clear. I did not want to bloat this post. Hence I only gave the links to the actual solution at the end of the post. I was hoping people familiar with the problem will recognize it without going into the actual solution. As for my goal, it is simply to solve this problem as I am brushing up on my Algorithms.

[edit - Peter_in_2780] fixed URLs in links to solutions.[/edit]
Posted
Updated 13-Aug-12 16:01pm
v3

I only read the first solution you linked to, but I'm guessing the other one uses the same mathematicians' shorthand. If you read it carefully, they take the left partition to recurse on, and imply that the same process is done on the right. (In fact, reading it again, they actually state that explicitly in at least two places.)

So basically, they are using the left partition AS THE EXAMPLE just so they have a name to use as they describe the recursive step.
If I was standing in front of a blackboard explaining it, I could just point and say "this one", but that's a bit hard to do in a paper.

Cheers,
Peter

p.s. I edited your question to fix the links.
 
Share this answer
 
Because in the original partition algorithm in the book, for each element k in the left partition, k <= x; While for each element k in the right partition, k > x.

That's why the left partition can be further partitioned to LEFT and MIDDLE. By the way, this improvement has nothing to do w/ interval sorting. It can be applied to normal quicksort as well, just that it's less likely to have as many equal elements as in interval sorting where intersection really means equality.
 
Share this answer
 

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900