8.3 A Dynamic Collision Detection System 469
lists. For general input it is O(n
2
), but for nearly sorted data it is O(n + e),where
e is the number of exchanges used by the algorithm. Pseudocode for the insertion
sort is
// input: A[0] through A[n-1]
// output: array sorted in-place
void InsertionSort (int n, type A[])
{
for(j=1;j<n;j++)
{
key = A[j];
i=j-1;
while(i>=0andA[i] > key )
{
Swap(A[i],A[i+1]);
i--;
}
A[i+1] = key;
}
}
The situation so far is that we have applied the sort-and-sweep algorithm to
our collection of intervals, a once-only step that requires O(n log n + m) time. The
output is a set S of pairs (i, j)that correspond to overlapping intervals, I
i
∩I
j
.Some
intervals are now moved, and the list of endpoints is re-sorted in O(n + e) time. The
set S