Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: Algorithms
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
AmitDey17.1K
Edited 13-Aug-12 16:01pm
v3
Rate this: bad
good
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.
 
Cheers,
Peter
 
p.s. I edited your question to fix the links.
  Permalink  
Rate this: bad
good
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.
  Permalink  

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

  Print Answers RSS
0 Sergey Alexandrovich Kryukov 392
1 OriginalGriff 370
2 CPallini 190
3 Abdul Samad KP 145
4 George Jonsson 119
0 OriginalGriff 6,329
1 Sergey Alexandrovich Kryukov 5,700
2 CPallini 4,940
3 George Jonsson 3,469
4 Gihan Liyanage 2,522


Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 10 Apr 2014
Copyright © CodeProject, 1999-2014
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