Algorithms and Data StructuresTopicsNoteLinear SearchLinear Search - exampleSlide 6Binary SearchSlide 8QuicksortPartitionSlide 11SwapLibrariesqsort – standard C libraryqsort (int)qsort (strings)Big “Oh”Timingnlog n vs. n2Growing ArraysGrowing Arrays in CSlide 22ListsLists in CSlide 25Append Element to Back of ListLookup Element in ListApply Function to Elements in ListPrint Elements of a ListCount Elements of a ListFree Elements in ListDelete Element in ListTreesBinary Search TreeBinary Search Tree LookupHash TablesHash TableHash Table LookupHash FunctionStandard Template LibraryIteratorsperlJava CollectionAlgorithms and Data StructuresObjectives: To review the fundamental algorithms and data structures that are commonly used in programs. To see how to use and implement these algorithms and data structures in different languages and to see what language and library support exists for them.Sorting and SearchingArrays and VectorsListsHash TablesGeneric programmingTopicsVectors (Arrays)ListsBinary SearchQuicksortHash Tables - DictionariesC, C++, Java, PerlNotePython will be used as the instructional language in this document.It is simple enough to follow. Where "Python details" are used, they will be explained.Linear SearchJust exhaustively examine each elementWorks on any list (sorted or unsorted)Only search for a linked-listExamine each element in the collection, until you find what you seek, or you've examined every elementNote that order of examination doesn't matterLinear Search - exampleL = range( 1, 11 ) # fill w/numbers 1-10random.shuffle( L ) # mix it upbFound = FalseLinear Search/* lookup: sequential search for name in tab;return index */int lookup(char *name, Nameval tab[], int ntab){ int i; for (i = 0; i < ntab; i++) if (strcmp(name, tab[i].name) == 0) return i; return –1; /* no match */}Binary SearchOnly works on sort ed collectionsOnly works on indexed collections (arrays, vectors)Start in the middle:Find it?Cut search space in ½Need θ(lg(n)) time, worst (and avg.)Binary Search/* lookup: binary search for name in tab; return index or –1 if not found. */int lookup(char *name, Nameval tab[], int ntab) { int low, high, mid, cmp; low = 0; high = ntab – 1; while (low <= hight) { mid = (low + high)/2; cmp = strcmp(name, tab[mid].name); if (cmp < 0) high = mid – 1; else if (cmp > 0) low = mid + 1; else /* found match */ return mid; } return –1; /* no match */}Quicksortpick one element of the array (pivot)partition the other elements into two groupsthose less than the pivotthose that are greater than or equal to the pivotPivot is now in the right placerecursively sort each (strictly smaller) groupPartitionunexaminedplast i n-1unexamined< pp >= p0 1 last i n-1< p p >= p0 last n-1Quicksort/* quicksort: sort v[0]..v[n-1] into increasing order. */void quicksort(int v[], int n){ int i, last; if (n <= 1) /* nothing to do */ return; swap(v, 0, rand()%n); /* move pivot element to v[0] */ last = 0; for (i = 1; i < n; i++) /* partition */ if (v[i] < v[0]) swap(v, ++last, i); swap(v, 0, last); /* restore pivot */ quicksort(v, last); /* recursively sort each part. */ quicksort(v+last+1, n-last-1);}Swap/* swap: interchange v[i] and v[j]. */void swap(int v[], int i, int j){ int temp; temp = v[i]; v[i] = v[j]; v[j] = temp;}LibrariesC: qsortC++: sort (algorithm library from STL)java.util.collections.sortperl: sortqsort – standard C libraryqsort( void *a, int n, int s,int(*cmp)(void *a, void *b) );Sorts array a, which has n elementsEach element is s bytescmp is a function that you must providecompares 2 single elements, *a & *bqsort must pass pointers, since it doesn't know type (but cmp does, since you provide it for a given sort)returns -1 if a<b, 0 if a==b, and 1 if a>bFor sorting in descending order, return 1 if a < bqsort (int)int arr[N];qsort(arr, N, sizeof(arr[0]), icmp);/* icmp: integer compare of *p1 and *p2 */int icmp(const void *p1, const void *p2){ int v1, v2; v1 = *((int*) p1); v2 = *((int*) p2); if( v1 < v2 ) return –1; else if( v1 == v2 ) return 0; else return 1;}qsort (strings)char *str[N];qsort(str, N, sizeof(str[0]), scmp);/* scmp: string compare of *p1 and *p2 *//* p1 is a ptr to a string, or char*, so is a *//* ptr to a ptr, or a char** */int scmp(const void *p1, const void *p2){ char *v1, *v2; v1 = *((char**) p1); v2 = *((char**) p2); return strcmp(v1, v2);}Big “Oh”Notation Name ExampleO(1) constant array indexO(log n) logarithmicbinary searchO(n) linear string comparisonO(nlog n) n log n quicksort/mergesortO(n2) quadratic insertion sortO(n3) cubic matrix multiplicationO(2n) exponentialset partitioning*It is more precise to use for order classesTimingUnix time command[jjohnson@ws56 lec1]$ time sign < /usr/share/dict/words | sort | squash > temptime 0.11user 0.01system 0:00.27elapsed 43%CPU (0avgtext+0avgdata 0maxresident)k0inputs+0outputs (91major+13minor)pagefaults 0swapsclock()counting cyclesnlog n vs. n2Growing ArraysArrays provide O(1) access and insertion timeSorted arrays provide O(log n) search time and O(n) insertion time [have to move elements]If the number of elements in an array is not known ahead of time it may be necessary to resize the array.Involves dynamic memory allocation and copyingTo minimize the cost it is best to resize in chunks (some factor of its current size)Growing Arrays in Ctypedef struct Nameval Nameval;struct Nameval { char *name; int value;};struct NvTable { int nval; /* current number of values */ int max; /* allocated number of values */ Nameval *data; /* array of name-value pairs */};enum { NVINIT = 1, NVGROW = 2 };struct NvTable symList;Growing Arrays/* addname: add new name and value to symList */int addname( Nameval newname ) { Nameval *nvp; if( symList.data == NULL) { /* first time */ symList.dat =(Nameval*) malloc(NVINIT * sizeof(Nameval)); if( symList.dat == NULL ) /* check for no memory */ return –1; symList.max = NVINIT; symList.nval = 0; } else if( symList.nval >= symList.max) { /* grow */ nvp = (Nameval*) realloc( symList.data,(NVGROW*symList.max)*sizeof(Nameval)); if( nvp == NULL ) /*
View Full Document