New answers tagged sorting
0
I think the number of comparisons is minimised by splitting an array into sub arrays in the following way:
Let N = 2^k + j, 0 <= j <= 2^k.
If j <= 2^(k-1) then split into subarrays of size 2^(k-1) and 2^(k-1) + j.
If j >= 2^(k-1) then split into subarrays of size j and 2^k.
The number of comparisons is at most (k+1)N + 1 - 2^(k+1).
0
You can merge two sorted arrays with a total of N items to one sorted array with at most (N-1) comparisons. To be exact, in N-k steps if the k largest elements are in the same of the two arrays.
We can show be induction that for every k, if N <= 2^k then any array of N elements can be sorted with N * k comparisons. This is obviously true for k=0 and k=1. ...
0
The inductive proof doesn't actually use the formula $C_N = N\lg N$ for $N = 2^n$. Rather, once we know that the solution is about $N\lg N$, we can just prove it by induction, as I show below. But first, let me comment that it is easy to prove by induction that $C_N$ is monotone, and so conclude that $C_N = \Theta(N\log N)$, by approximating $N$ above and ...
2
You can use quickselect, which has expected linear time complexity. (There's a version using the median-of-medians partitioning algorithm which has worst-case linear time complexity, but it's usually a lot slower in practice.) Note that if there are duplicate elements in the two arrays, it might not be possible to satisfy the strict less-than constraint ...
-1
Concatenate A and B into one array C with a total length of 2n. You start with the partition [1, 2n] of C with the goal to make the first l items less than the last r items, l = r = n initially.
As long as your partition has length 2 or more: Pick a random pivot element. Partition into two partitions of length x and y, like in quick sort. If x <= l then ...
1
You could sort them and then iterate over them. Sorting is $n\log n$ and then it would only take one more pass to go check them because once you've passed an element, you know you've done all the swapping you need for that element.
0
You haven't defined what you mean by average, so let me assume that the average is taken over all permutations of some fixed array consisting of three distinct numbers (the exact numbers don't matter, since the result will be the same).
Denote the number of comparisons performed on an array $A$ by $C(A)$. Then the average number of comparisons is
$$
\frac{C(...
1
The first equation is the base case for the recurrence. The second equation represents the recurrence formula, on everything that isn't a base case.
Now, you can prove by induction this statemen, simply by using complete induction as follows:
The base case is obviously correct. For the induction hypothesis, assume correctness for any $k<n$.
Now, for $T(n)$...
1
The analysis questioned in Problem 3 assumes(?) an implementation closer to ACM Algorithm 64 than to what Sedgewick is getting at (as does "Problem 1"): recursion on all partitions, not "iteration on the biggest one".
1
For quick sort, you end up with quadratic runtime only if you use the most stupid method of picking a pivot- by taking the first or last element. Picking the middle element, or the median of first, last and middle element, it will run nicely fast because for all except 2k elements we have just comparisons, and nothing will be moved. Still n log n, but with a ...
1
The complexity of sorting a $k$-sorted array is actually $\Theta(n\log (k+1))$. Given a $k$-sorted array, you can use a modification of heapsort to sort it using only $O(n\log (k+1))$ comparisons. You put the first $2k$ elements in a heap, and you then repeatedly add the next element to the heap, and extract the minimum element from the heap. After ...
2
Probably that statement does not come from the same source where you got the pseudocode from. Another common way to define Bubblesort is the following:
procedure bubblesort
sorted := false
while not sorted
sorted := true
for j := 1 to n − i
if a[j] > a[j+1] then
swap a[j] and a[j+1]
...
6
One huge advantage of s stable sorting Algorithm is that s user is able to first sort a table on one column, and then by another.
Say that you have a website like Wikipedia with some tabular data, say a list of sorting algorithms, two of the columns being year and name. If you want to have that table sorted by year, and then alphabetically by name, you can ...
0
There are a number of spatial index solutions that can be used with 3D data. Most indexes belong to one of these groups: Quadtrees, R-trees and kD-trees and Locality Sensitive Hashing.
Most of these have floating point implementations, but they should work fine (or should be easily adaptable) to integer coordinates.
Many implementations support nearest ...
0
In the 1960s and even a bit later sorting took up a lot of time. Part of the problem, back then, was the size of main memory (RAM if you like) was small and often the list of records you wanted to sort would not fit in RAM. As a result, the sort algorithm had to read and write the same record several times. Today, just about all files fit in memory.
Today ...
Top 50 recent answers are included