Algorithms and Data Structures Objectives 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 Searching Arrays and Vectors Lists Hash Tables Generic programming Topics Vectors Arrays Lists Binary Search Quicksort Hash Tables Dictionaries C C Java Perl Note Python 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 Search Just exhaustively examine each element Works on any list sorted or unsorted Only search for a linked list Examine each element in the collection until you find what you seek or you ve examined every element Note that order of examination doesn t matter Linear Search example L range 1 11 fill w numbers 1 10 random shuffle L mix it up bFound False Linear 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 Search Only works on sorted collections Only 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 Quicksort pick one element of the array pivot partition the other elements into two groups those less than the pivot those that are greater than or equal to the pivot Pivot is now in the right place recursively sort each strictly smaller group Partition p unexamined last i p 0 n 1 p 1 last p 0 p unexamined i p last n 1 p n 1 Quicksort 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 Libraries C qsort C sort algorithm library from STL java util collections sort perl sort qsort standard C library qsort void a int n int s int cmp void a void b Sorts array a which has n elements Each element is s bytes cmp is a function that you must provide compares 2 single elements a b qsort 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 b For sorting in descending order return 1 if a b qsort 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 O 1 O log n Name Example constant array index logarithmi binary search c O n linear string comparison O nlog n n log n quicksort mergesort O n2 quadratic insertion sort O n3 cubic matrix multiplication O 2n exponenti set partitioning alto use for order classes It is more precise Timing Unix 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 k 0inputs 0outputs 91major 13minor pagefaults 0swaps clock counting cycles nlog n vs n2 Growing Arrays Arrays provide O 1 access and insertion time Sorted 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 copying To minimize the cost it is best to resize in chunks some factor of its current size Growing Arrays in C typedef 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 realloc failed return 1 symList max NVGROW symList data nvp symList data symList nval newname return symList nval Lists A sequence of elements Space is allocate for each new element and consecutive elements are linked together with a pointer O 1 time to insert at front O n to append unless pointer to last element kept O n traversal time head NULL data 1 data 2 data 3 data 4 Lists in C typedef struct Nameval Nameval struct Nameval char name int value Nameval next in list newitem create new item from name and value Nameval newitem char name int value Nameval newp newp Nameval emalloc sizeof Nameval newp name name newp value value newp next NULL return newp Lists in C addfront add newp to front of listp Nameval addfront Nameval listp Nameval newp newp next listp return newp nvlist addfront nvlist newitem smiley 0x263A Append Element to Back of List addend add newp to end of listp return ptr to new list Nameval addend Nameval listp Nameval newp Nameval p if listp NULL return newp for p listp p next NULL p p next p next newp return listp Lookup Element in List lookup sequential search for name in listp Nameval lookup Nameval listp char name for listp NULL listp listp next if strcmp name listp name 0 return listp return NULL no match Apply Function to Elements in List apply execute fn for each element …
View Full Document
Unlocking...