New answers tagged sorting
2
What you are looking for is a comparison sort. Please take a look at that article.
Let us state clearly the requirement for any two given objects, object i and object j when they appear in the final sorted list. Object i should occur before object j if Z(i, j) = 1. Object i can occur before or after object j if Z(i, j) = Z(j, i) = 0.
As vonbrand mentioned, ...
2
Here's a way to sort points by angle in Swift:
let radarSortedPoints: [CGPoint] = points.sorted { pointA, pointB -> Bool in
atan2(pointA.y, pointA.x) < atan2(pointB.y, pointB.x)
}
9
For each of your points in the field, calculate the red angle:
Then sort all the (point, angle)-tuples by the angle.
1
I'll give you a simple example.
Suppose you have some floating-point numbers to add together. We'll assume they're all non-negative so that cancellation isn't an issue.
For the purpose of this example, I'm going to use decimal with four significant digits of precision just to illustrate the point.
The numbers are:
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1....
3
The question only says that the target list needs to be maintained in sorted order. It doesn't say anything about any other data structure that you may choose to use. The proposed solution first does some preprocessing of the arguments to insert, then does the insertion proper. This is allowed by the problem statement.
A practical reason to do this, rather ...
answered Feb 22 at 23:50
Gilles 'SO- stop being evil'
37.8k7 gold badges101 silver badges166 bronze badges
-1
It should be O(n).
Follow the algorithm as -
1) If Linked list is empty then make the node as
head and return it.
2) If the value of the node to be inserted is smaller
than the value of the head node, then insert the node
at the start and make it head.
3) In a loop, find the appropriate node after
which the input node is to be inserted.
To ...
0
It really is a tricky question. First of all, the complexity of O(nlogn) applies only for the algorithms which use comparison between their elements (comparative algorithm). There are also algorithms which are non-comparative such as Radix sort which their complexity depends on the size in bits which the numbers need to be stored in memory. So if we assume ...
0
Best possible structure which I know of, are Fibonacci Heaps, you can insert elements in $O(1)$ and extract the minimum in $O(\log(n))$, this means if you need a sorted order of all elements it takes you $O(n\log(n))$ while inserting new elements only costs you $O(1)$, I know no other structure which could keep up with this.
4
The other answers provide correct solutions. However, you can do a bit better considering multivariate complexity. Note that the provided running times in the other answers are not quite specific since they ignore either the size of the first array or the lengths of the strings.
Here are 2 different methods with their specific running times. The first of ...
2
I think a straightforward way to accomplish this would be to create a mapping of every element in your ordering list to its index i.e. order["three"] = 3. Then your comparator for sorting two objects a and b in the input is order[a] <= order[b]
This way, you can easily abstract the pairwise comparisons. For example both Python and C++ (and probably many ...
2
Assuming the length of both arrays in your question is $\mathcal{O}(n)$, then in terms of required string comparisons:
Create an array of the form inverse = [("one", 1), ("two", 2), ("three", 3)] where the additional indices are the array indices and sort it lexicographically on the first pair elements. This can be done in $\mathcal{O}(n \ln n)$ string ...
4
Suppose you have an array $A = [e^0, e^1, e^2, \dots]$. You do a search in this array, and try to find the biggest value in the array that's smaller than or equal to $x$.
You find this value at position $n$. What is the value of $A[n]$?
What can you say about $\ln(x)$ in relation to $n$?
Can you find the correct $n$ quickly? Does it help that $A$ is sorted?
1
What do you mean by "practice sorting"? Sets of data to sort by hand? Just whip something up with a random number generator. Examples showing how the methods work? At least Wikipedia has detailed algorithms with pretty animations, or search for "algorithm animation", it is quite popular.
0
So you learnt that Quicksort takes quadratic time for an already sorted array.
Exercise 1: implement Quicksort so it takes O(n log n) for a already sorted array.
Exercise 2: implement Quicksort so it takes linear time in this case.
6
Meanwhile knowing how "sorted" an array is gives some information about the array and might help sorting it more efficiently, it is not quite right, that quick-sort runs in $O(n^2)$ if the array is sorted. The running time of quick-sort depends on the pivoting rule and your statement holds only if we always choose the first (or last) element as the pivot. A ...
2
In more detail, this variant of bubble sort finds the leftmost pair of adjacent items that are in the wrong order. Then it swaps those two items. This operation of "find and swap" is repeated until the given list is sorted. In other words, this variant of bubble sort swaps the items in the leftmost inversion of the given list repeatedly until the given list ...
0
Here is the general idea:
Sort all the strings according to their first character (refer to each string using an index to save time).
Partition the strings according to their first character, and run recursively on each part (deleting in your mind the first character).
I'll let you work out the details.
0
I think $F$ and its details are irrelevant, an appropriate comparison function that uses $F$ internally turns your problem into a regular sorting one. Then your problem is solved in $O(n)$ using a regular selection problem.
Find the element with rank $pk$ in $O(n)$ using a selection algorithm. Similarly find the element with rank $(p+1)k$. Then do a single ...
0
Your analysis looks correct to me. The answer should be N-2, not 2(N-1).
It wouldn't be unheard of for graders/teachers to work with an incorrect solution.
0
You can't satisfy both goals. Suppose $A=[10,20,30]$ and $B=[10,20,30]$; then you presumably want the modified $B$ to be $[10,20,30]$. Now suppose $A=[10,20,30]$ and $B=[10,30,20]$; then you presumably want the modified $B$ to be $[10,20,30]$. The original A and the modified B are the same in both cases, so there is no way to tell from them what the ...
0
Do not even mention big-O here because that is for asymptotic behaviour and f(1000) doesn’t give you the slightest clue what f(2000000) would be.
You are given that the runtime is f(n) = c x g(n) for three different functions c. Given the value of c x g(1000) for the first function g, you calculate c. Then you substitute c and n for all the cases.
Top 50 recent answers are included
