hi do we have binary sort algorithm ? like merge sort or the other kinds of sorts do we have binary sort?? is there any kind of sorts that its name is binary sort? thanks
+1
A:
There's this and there's binary insertion sort. The two are pretty similar. They're both quadratic (O(n^2)) time algorithms.
Both algorithms do O(n log n) number of comparisons, but in practice you would also have to move elements around, which would make the entire algorithm quadratic.
IVlad
2010-06-19 08:16:16
I want to write an algorithm(this is not a home work) and I want to sort at first and then using binary serach for finding two elements that their sum equal to 9 and the running time of this algorithm should be theta(nlogn) can I use merge sort for sorting and Binary search for searching?
2010-06-19 08:26:22
also thanks for your help!!!
2010-06-19 08:27:46
@matin1234:nope.but you can remove the numbers more than 8.and sort the left numbers, loop from up and down(it is a little strange) for numbers resulting a sum of nine.it is O(n).
Behrooz
2010-06-19 08:31:39
@matin1234 - yes you can. For each element `i` binary search in `[i + 1, n]` for an element equal to `9 - a[i]`. This is after sorting of course. @Behrooz - `100 + (-91) = 9`.
IVlad
2010-06-19 08:52:13
aha ,|V|ad thanks a lot I get the whole!!
2010-06-19 08:59:10
A:
There are some sort's that involve splitting into two peices (merge sort) but I don't beleive that there is a sort called exactly "binary sort".
thomasfedb
2010-06-19 08:25:58
A:
We do not have a binary sort algorithm, but we do have binary search on a sorted array.
agsamek
2010-06-19 08:27:04
A:
Not sure what your looking for but if your looking for a suitable binary sort algorithm then you want to be aware of your requirements. Each algorithm has its own strengths and weakness.
For example, are you looking for an algorithm that give fastest average performance (e.g. heap search) or fasted worst case (slowest operation) performance (e.g. balanced binary tree). Some are slow if you also need to iterate from one item to the next. If your doing many random operations you are probably more interested in average performance but if you have a need to ensure that any operation is faster than X milliseconds then you may want a different algorithm. Some can be slow if you always adding items at the end of the collection etc.
So have a google for keywords like:
- Red black tree
- heap search
- balanced trees, e.g. http://www.codeproject.com/KB/recipes/redblackcs.aspx?msg=931557
It all comes down to what you need.
Rob Smyth
2010-06-19 08:32:21