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 ...
answered Dec 31 '20 at 14:11
Yuval Filmus
241k2020 gold badges243243 silver badges426426 bronze badges
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
Related Tags
sorting × 730algorithms × 431
algorithm-analysis × 143
runtime-analysis × 86
time-complexity × 78
arrays × 60
quicksort × 56
complexity-theory × 42
data-structures × 39
lower-bounds × 33
radix-sort × 30
efficiency × 25
mergesort × 22
optimization × 20
graphs × 19
heaps × 17
asymptotics × 15
permutations × 15
randomized-algorithms × 14
reference-request × 13
comparison × 12
search-algorithms × 11
terminology × 10
strings × 10
probability-theory × 10