Tute03 - 07s2 COMP1921 Wiki - 0 views
-
int sequence[], int numElements
-
Filius Fob on 07 Aug 07This is a very common pattern in C, since C arrays don't secretly store the array length with the array as in some other languages. Thus, whenever an array gets passed to a function, so too does the array length.
-
-
for (i = 1; i < numElements; i++) {
-
-
swap(&sequence[j], &sequence[j - 1])
-
Notice the pointer operations here, namely '&' - the 'address-of' operator. It maps variables to their addresses. See the notes in week 2's tute.
-
- ...5 more annotations...
-
for (j = i; j > 0; j--) {
-
for (j = i; j > 0; j - > - > ) > { >
-
let j start from i and iterate down to 1. NB Not zero, since line 6 compares the jth and (j-1)the elements.
-
-
asymptotic
-
we have found the insertion point
-
How do we know this? Because as the algorithm runs the array is split in to two portions: a left and right one. The left one has indices 0..(i-1) and is always sorted. The right one is unsorted. (By 'left' and 'right', i'm assuming the array indices increase L to R - Western bias, sorry!) Thus, the insertion operation simply looks for the first element of the L portion less than the one being inserted. ie it's a linear search of a sorted array.
-
-
Move smallest element to the left