New answers tagged sorting
0
The other approach that I can think of is the obvious one: process the file one line at a time, and consult a dictionary of "seen" lines. What may not be obvious is how to represent the dictionary.
There are plenty of on-disk data structures that would work, and this is a well-researched area given that this is what databases do for a living. Some ...
2
I think you already have implemented some sort of adjacency list representation of a directed graph. You can use a topological sorting (https://en.m.wikipedia.org/wiki/Topological_sorting) to order the items.
2
Consider the recurrence
$$
T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0,
$$
which is one formalization of the worst-case running time of quicksort. Let us show by induction that the maximum is attained at $k = 0$ (or $k = n$). We will show this while at the same time showing that $T(n) = \frac{n(n+1)}{2}$.
The base case, $n=0$, is ...
0
This last term n should, more precisely, be n-1, not n. It arises out of the fact that for splitting the array into 2 parts: one part consisting of all elements smaller than pivot and another consisting of all elements greater than or equal to pivot, we have to perform exactly n-1 (comparison) operations.
Top 50 recent answers are included
