0

I have been exposed to a lot of sorting algorithms lately: from bubble sort to radix and counting sort, but there is a particular problem for which I do not know what is legal to do or not. (I'm still in the pseudo-code writing phase, so I am not yet writing the algs in code languages and running tests- thus my security about what is 'legal' and what is not, is kinda shaky.)

The problem is about sorting a list of intervals with respect to the start-point: for example: sorting List1 = [[1,4] , [7, 17], [5, 10]] For the particular algorithm I've designed, I need them to be sorted into something like: [[1,4] , [5, 10], [7, 17]]

I thought of doing radix sort backwards, but I read that radix sort is specifically for digits ordering. It does look like I could use bucket sort too, but we didn't learn about bucket sort in class...

Edit1: There is a time efficiency i need to worry about, so that's why I'm not doing the most straightforward solution and compare all List1[i][0] for i in range(list1)

Improve this question
7
  • ...why don't you just sort by the start point, and ignore the end point? Then you just sort the set of start points by any algorithm you know already. Commented Sep 30, 2013 at 17:19
  • well, yea, but i have to be careful with how much time it takes Commented Sep 30, 2013 at 17:20
  • 1
    I hope "from bubble sort to radix and counting sort" includes quick-sort and merge-sort. Commented Sep 30, 2013 at 17:21
  • 1
    Will you be sorting millions of intervals? If no, then you don't need to worry that much: any O(n log n) algorithm will be fine in pseudocode. (Practical implementation concerns demand that you use a nice algorithm like quick, intro, merge, or heap sort). Commented Sep 30, 2013 at 17:21
  • 2
    Unclear what you are asking about - any sorting algorithm can order sequences of elements if you provide comparison function. If you need to pick one throw a dice... Commented Sep 30, 2013 at 17:21

1 Answer 1

Reset to default
1

I suppose that the interval start points can be any real numbers, in that case I would advise you to use a Comparison based sort (insertion,selection,bubble,merge,heap,or quick) instead of Distribution sort (radix, counting or bucket). Though comparison based sorts have a lower bound of O(nlogn) but they can be used in any general case as compared to O(n) sorts like counting/ bucket which require input to be in some specific range.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.