Skip to main content

Home/ Groups/ UNSW_comp1921_07s2
Rss Feed
Sort By: Most Recent | Popular Filter: All | Bookmarks | Topics Simple Middle
Filius Fob

Tute03 - 07s2 COMP1921 Wiki - 0 views

cgi.cse.unsw.edu.au/...Tute03

analysis complexity program time

shared by Filius Fob on 07 Aug 07 - No Cached
  • int sequence[], int numElements
    • Filius Fob
      Filius Fob on 07 Aug 07
       
      This 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++) {
    • Filius Fob
      Filius Fob on 07 Aug 07
       
      let i traverse over all elements except the very first
  • swap(&sequence[j], &sequence[j - 1])
    • Filius Fob
      Filius Fob on 07 Aug 07
       
      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 - > - > ) > { >
    • Filius Fob
      Filius Fob on 07 Aug 07
       
      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
    • Filius Fob
      Filius Fob on 07 Aug 07
       
      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
1 - 1 of 1
Showing 20▼ items per page
Join this group