New answers tagged sorting
0
Well. If you considered only the asymptotic time complexity $\mathcal{O}(\mbox{N log N})$, then there would be practically no difference between Quick and Heap sort. So both algorithms runtime is:
$\mbox{constant} \cdot \mbox{N log N}$
but, the constant may differ significantly and this is what makes a big difference. So, in practice, Quick sort is much ...
-1
i was thinking quicksort. you select as pivot the element that just happens to be the middle element. compare the pivot to the remaining 4 items resulting in two piles to be sorted. each of those piles can be sorted in 1 comparison. unless i have made a terrible mistake, the 5 items were fully sorted in just 6 comparisons and i think that is the absolute ...
0
Let us start with the subroutine PARTITION. The loop maintains the following invariant:
$A[k] \geq x$ for all $k \geq j$, and $A[k] \leq x$ for all $k \leq i$.
If the loop ever terminates, then the two ranges "$k \geq j$" and "$k \leq i$" cover the entire array, and in particular, $A[k] \leq x$ for all $k \leq j$, and $A[k] \geq x$ for all $k \geq i \geq ...
0
In order to get the files in the desired order, simply follow the following rule: A node can be deleted iff all of its children have been deleted. This is the same as a postorder traversal of a tree.
Let's say you use a container $S$ for your search structure (stack for DFS or queue for BFS). Now, we create a stack $T$ which will in the end will be the ...
0
I'm not sure about the algorithm modification to directly call the callback function in a reverse order, but I found a way to do this without extra memory allocation.
My solution is to embed a doubly linked list node within the data structure storing rules. (It actually turns out there was already a linked list node in the data structure I used for other ...
-1
I have built a new algorithm to find the minimal set M but I can't check whether the algorithm is correct or not. The algorithm is as follows:
1. Consider the new array formed by multiplying the abssica array and
the corresponding ordinate array and arrange it in ascending order.
Next we arrange the abssica array and the ordinate array
...
1
Stirling's formula shows that
$$
\binom{N}{pN} \sim \frac{2^{H(p)N}}{\sqrt{2\pi p(1-p)N}},
$$
where $H(p)$ is the binary entropy function:
$$
H(p) = p\log \frac{1}{p} + (1-p) \log \frac{1}{1-p}.
$$
In particular, this shows that for $k \geq 2$,
$$
\binom{kn}{n} = (1+o(1)) \frac{2^{H(1/k)kn}}{\sqrt{2\pi(1/k)(1-1/k)kn}} \geq (1+o(1)) \frac{2^{n\log k}}{\sqrt{2\...
1
This is an awful question for a test.
Selection sort always has about n^2/2 comparisons and n swaps. Insertion sort has between n and n^2/2 comparisons and the same number of swaps. But as you said absolutely correctly, the actual time depends on the exact implementation.
For example if you look for the smallest element in selection sort like this:
...
1
The meaning of $O(n^2)$
I was told that the complexity of bubble sort is $O(n^2)$. But when I run with a reversed list (worst case) with size 3, the counter finishes with the value 12, shouldn't it be 9?
Had $O(n^2)$ meant $n^2$, we should have written it as $n^2$ instead of that funny looking $O(n^2)$. Instead, $O(n^2)$ means no more than $n^2$ roughly. ...
0
There are n! ways how n items in an array can be arranged. If you have k comparisons each with two possible outcomes, then you have a total of $2^k$ possible outcomes.
Therefore, if $2^k < n!$, there are at least two different arrangements of the data where all comparisons produce the same result. Since you cannot know which arrangement of data you have,...
0
The statement is not quite rigorous. Sorting requires at least $\lg(n!)$ comparisons in the worst case. Because you can very well design an algorithm that would check that the array is already sorted and stop if true. Such an algorithm would indeed sort a sorted array in $n-1$ comparisons.
This said, you can permute an array of $n$ elements in $n!$ ways, ...
Top 50 recent answers are included
