Sorting Many Sorting Algorithms numerical order lexical error other 2010 Goodrich Tamassia Iterators and Sequences 1 Sorting Selection Sort Very simple Big O For speed Big O for memory 2010 Goodrich Tamassia Iterators and Sequences 2 Sorting Selection Sort in place sort divide the list into two parts Sorted part of the list Unsorted part of the list Initially the sorted list is NULL Pick the smallest item or largest Put this at the end of sorted part of the list Continue until the unsorted part of the list is NULL 2010 Goodrich Tamassia Iterators and Sequences 3 Sorting Selection Sort Example Sort in ascending order 43 12 65 26 5 15 smallest 5 12 65 26 43 15 now find smallest in rest of list smallest 5 12 15 26 43 65 sorted 2010 Goodrich Tamassia Iterators and Sequences 4 Sorting Selection Sort We write two versions Array based Linked list based 2010 Goodrich Tamassia Iterators and Sequences 5 bubble Sort Step through the list Compare adjacent pair if in wrong order swap Continue until no more swaps needed 2010 Goodrich Tamassia Iterators and Sequences 6 bubble Sort Example bubble sort ascending order First Pass through 43 12 65 26 5 15 12 43 65 26 5 15 12 43 26 65 5 15 12 43 26 5 65 15 12 43 26 5 15 65 the array swap swap swap swap 43 65 65 65 12 26 5 15 First pass complete 2010 Goodrich Tamassia Iterators and Sequences 7 bubble Sort Example bubble sort ascending order Second pass through the array 12 43 26 5 15 65 12 26 43 5 15 65 swap 43 26 12 26 5 43 15 65 swap 43 5 12 26 5 15 43 65 swap 43 15 Second pass over 2010 Goodrich Tamassia Iterators and Sequences 8 bubble Sort Example bubble sort ascending order Third pass through the array 12 26 5 15 43 65 12 5 26 15 43 65 swap 26 5 12 5 15 26 43 65 swap 26 15 Third pass over 2010 Goodrich Tamassia Iterators and Sequences 9 bubble Sort Example bubble sort ascending order Fourth pass through the array 12 5 15 26 43 65 5 12 15 26 43 65 swap 12 5 Fourth pass Do one more pass to see there is no swap Total of 5 passes 2010 Goodrich Tamassia Iterators and Sequences 10 bubble Sort Example bubble sort ascending order 23 7 45 13 64 9 3 2010 Goodrich Tamassia Iterators and Sequences 11 selection Sort Array list Modify the selection sort algorithm for Arrays So that you swap the element rather than just swap values 1 Same for bubble sort Iterators and Sequences 12 Iterators and Sequences 2010 Goodrich Tamassia Iterators and Sequences 13 Containers and Iterators An iterator abstracts the process of scanning through a collection of elements A container is an abstract data structure that supports element access through iterators An iterator behaves like a pointer to an element begin returns an iterator to the first element end return an iterator to an imaginary position just after the last element p returns the element referenced by this iterator p advances to the next element Extends the concept of position by adding a traversal capability 2010 Goodrich Tamassia Iterators and Sequences 14 Containers Data structures that support iterators are called containers Examples include Stack Queue Vector List Various notions of iterator standard iterator allows read write access to elements const iterator provides read only access to elements bidirectional iterator supports both p and p random access iterator supports both p i and p i 2010 Goodrich Tamassia Iterators and Sequences 15 Iterating through a Container Let C be a container and p be an iterator for C for p C begin p C end p loop body Example with an STL vector typedef vector int iterator Iterator int sum 0 for Iterator p V begin p V end p sum p return sum 2010 Goodrich Tamassia Iterators and Sequences 16 Implementing Iterators Array based array A of the n elements index i that keeps track of the cursor begin 0 end n index following the last element Linked list based doubly linked list L storing the elements with sentinels for header and trailer pointer to node containing the current element begin front node end trailer node just after last node 2010 Goodrich Tamassia Iterators and Sequences 17 STL Iterators in C Each STL container type C supports iterators C iterator read write iterator type C const iterator read only iterator type C begin C end return start end iterators This iterator based operators and methods p access current element p p advance to next previous element C assign p q replace C with contents referenced by the iterator range p q from p up to but not including q insert p e insert e prior to position p erase p remove element at position p erase p q remove elements in the iterator range p q 2010 Goodrich Tamassia Iterators and Sequences 18 Sequence ADT The Sequence ADT is the union of the Array List and Node List ADTs Elements accessed by List based methods Index or Position Generic methods size empty ArrayList based methods at i set i o insert i o erase i 2010 Goodrich Tamassia begin end insertFront o insertBack o eraseFront eraseBack insert p o erase p Bridge methods Iterators and Sequences atIndex i indexOf p 19 Linked List Implementation A doubly linked list provides a reasonable implementation of the Sequence ADT Nodes implement Position and store element link to the previous node link to the next node Special trailer and header nodes header Position based methods run in constant time Index based methods require searching from header or trailer while keeping track of indices hence run in linear time nodes positions trailer elements 2010 Goodrich Tamassia Iterators and Sequences 20 Array based Implementation elements We use a circular array storing positions A position object stores Element Index Indices f and l keep track of first and last positions 0 1 3 positions S f 2010 Goodrich Tamassia 2 Iterators and Sequences l 21
View Full Document
Unlocking...