Click here to Skip to main content
13,352,879 members (81,556 online)
Rate this:
Please Sign up or sign in to vote.
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.

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

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 22:48pm
Updated 13-Aug-12 17:01pm
Rate this: bad
Please Sign up or sign in to vote.

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.


p.s. I edited your question to fix the links.
Rate this: bad
Please Sign up or sign in to vote.

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.

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

  Print Answers RSS
Top Experts
Last 24hrsThis month

Advertise | Privacy |
Web04 | 2.8.180111.1 | Last Updated 14 May 2015
Copyright © CodeProject, 1999-2018
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100