New answers tagged sorting
2
Let's start with the case $k = 2$, and assume that the algorithm is comparison-based.
I claim that any algorithm that finds even a single element appearing $n/2$ times must know an index $i$ such that $A[i+1] = A[i+n/2]$. Indeed, suppose that this is not the case, and let us assume for simplicity that the entries of $A$ are real numbers. Let us say that the ...
1
This is a comment
There is a confusion when you say that sorting is creating the correct total order. When sorting, the total order is input as the relation $\geq$. What sorting does is output the order-preserving map from the natural numbers $0,1,2,...$ to the totally ordered set (or multiset) that was input. Typically, when this is implemented the map is ...
1
This is a very well-known problem, known as topological sorting.
Often it is difficult to find material on a subject because we don't know the proper terms to look for. That's why we have sites such as this.
0
place the pindex point to the last index in the array.Compare each and every element with pivot if the element is greater the pivot swap with pindex and decrement the pindex..The Following code helps you for the implementation of partition
def partioning(a,s,e):
pivot=a[s]
pi=e
for i in range(1,e):
if(a[i]>=pivot):
a[i],a[pi]=a[pi],a[i]
pi-=1
a[pi]...
0
Your example is an unfortunate one. Since you are sorting integers, you can pose a specific requirement to sort, such as the value, if that is the only thing to sort on you can use the radix sort, which would put the complexity at O(#ofdigitsn) or O(kn) which is 99% of cases is much better than lg(n), the only reason is sorting alrogithm isn't used more ...
0
For 1) Use any $O(n \log n)$-time sorting algorithm, like Mergesort. Without additional assumptions on the elements you cannot do better.
For 2) Use Radix sort with any base $b = n^\epsilon$ for any constant $\epsilon \in (0, 1]$ of your choice. For example pick $\epsilon =1$ so that $b=n$. The time needed for each iteration of Radix sort will be $O(n+b) = ...
1
The number of "work" being done, should be counted with the big-O notation. This means - that you count the while loop as $O(n)$ and any other constant work done (for example, the work after the while) is $O(1)$ and $O(n)+O(1)=O(n)$ so it wont make a difference.
Counting the "work" without big-O is not well-defined in the general case - so you should avoid ...
3
This algorithm has been previously published in literature; for a detailed worst-case runtime analysis, see [1], [2], and [3]. It is referred to as "Symmerge" or "merging by decomposition". When the two subarrays to be merged are both of length $n$, the algorithm runs in worst-case $O(n \log n)$-time and uses $O(\log n)$ space (due to recursion).
If we use ...
4
The problem requires $\Omega(\log n)$ accesses to memory even if you are promised that the target integer appears at most once. You can prove it using an adversary argument.
Say that the target is zero. If the first access to the array is left of center, answer $-1$, and mentally set the elements to the left to be $-2,-3,\ldots$. If the first access is ...
3
There are $n$ possible answers. Each comparison gives you at most one bit of information. You need at least $\lg n$ bits of information to describe the answer, so you'll need at least $\lg n$ comparisons.
Top 50 recent answers are included
