12,292,669 members (65,530 online)
Rate this:
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 11-Aug-12 21:48pm
AmitDey20.8K
Edited 13-Aug-12 16:01pm
v3

Rate this:

## Solution 1

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

Rate this:

## Solution 2

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.

Top Experts
Last 24hrsThis month
 Dave Kreskowiak 461 OriginalGriff 370 Richard MacCutchan 365 ppolymorphe 340 Sergey Alexandrovich Kryukov 279
 OriginalGriff 8,405 ppolymorphe 5,047 CHill60 4,960 KARTHIK Bangalore 4,437 Sergey Alexandrovich Kryukov 4,352