# Tag Info

2

I suspect that the question is looking for a non necessarily tight lower bound to the number of comparisons needed. The decision tree needs to be able to return the correct sorted sequence no matter what the initial permutation of the elements is. Therefore, it must have at least $n!$ leaves (one for each output permutation). Each internal vertex in the ...

2

I'm by no means an expert, but these points are more-or-less right, however, we often use merge-sort if we suspect the array to be near (reversely) sorted. Insertion sort is used in tiny lists (e.g. Java defines tiny to be less than 47), due to the fact that we have much less overhead in insertion sort than in merge sort and quicksort. As you may know, $O$ ...

2

It's unclear to me why you put the algorithms in that order. Also, "best work" is quite informal. There are many ways to compare sorting algorithm (worst-case time, expected-time, space complexity, etc). Some considerations that might help you are below. I can see how InsertionSort could be faster than MergeSort of QuickSort in practice for small ...

2

It would be $O(n)$, because each call to a siftdown or siftup procedure would be executed in $O(1)$ if well implemented. Indeed, in a maxheap, the siftdown procedure is called in the heapify procedure, or to extract a node from the tree, and is defined as follow: siftdown(x): while x is not a leaf and x is strictly smaller than its two children: ...

2

Since worst case space complexity of $\Theta(n)$ could be a problem, you can make a slight modification to the Qicksort algorithm: Partition the array, then sort the smaller half recursively, and sort the larger half iteratively. Roughly: Sort (range r) While r contains two or more elements Partition range r Sort (smaller sub partition) ...

1

Bucket sort will be slower if the data distribution is highly non-uniform. The primary advantage of bucket sort over other sorting algorithm is that it is faster when the data is uniformly distributed; so if the data is highly non-uniformly distributed, the advantages of bucket sort may evaporate.

1

Here is quicksort in a nutshell: Choose a pivot somehow. Partition the array into two parts (smaller than the pivot, larger than the pivot). Recursively sort the first part, then recursively sort the second part. Each recursive call uses $O(1)$ words in local variables, hence the total space complexity is proportional to the height of the recursion tree. ...

1

Quicksort is better unless the number of items in the wrong place is O(log n) only. There is a simple sorting algorithm that runs in O (n) if the number of items in the wrong place is a bit less than O (n / log n): Scan the array, and whenever two items are out of order put them into a separate array. Sort the separate array with Quicksort, then merge both ...

1

This problem is the optimization version of the partition problem, and if it was solvable efficiently, that would mean that $P = NP$. That means it is unlikely that there is a polynomial time solution to split an array in two. There are exact solution algorithms described on the wikipedia page, and some of them are in pseudo-polynomial time.

1

A little abstraction would help both reasoning about and solving the problem efficiently, I think. For every point $x$ on the circle, there is some set $S_x$ of pairwise overlapping arcs that intersect this point. Now, if there is some other point $y$ such that $S_x \subseteq S_y$, you can always use $y$ instead of $x$ in a solution to your problem. We can ...

Only top voted, non community-wiki answers of a minimum length are eligible