Data Struct&Algor EECS 281
Popular in Course
Popular in Engineering Computer Science
This 14 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 281 at University of Michigan taught by Sugih Jamin in Fall. Since its upload, it has received 10 views. For similar materials see /class/231525/eecs-281-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Data Struct&Algor
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
Outline HW3 is online Due Tue 1120 1 pm Last time a Design Patterns BruteForce and Greedy 0 Counting Change Problem 0 Pattern Matching Algorithms as Examples of 2 Design Patterns 0 Brute Force 0 Simplified BoyerMoore Today Sorting 0 Selection sort 0 Heap sort 0 lnsertion sort Sugih Jamin Gamineecsumich edu Sorting Objective rearrange items in list such that their keys are ordered according to some welldefined ordering rule eg numerical or alphabetical order Sort only when needed if you just need to know where every item is storing them in a dictionary hash table or BST will speed up lookup and allow for dynamic modification Sugih Jamin lamineecsumich edu Basic Operations and Concepts CMP compares items A and B SWAP swaps items A and B CMPSWAP compares and swaps if B is smaller than A Sort invariant an item is sorted if it is either 0 the last item in the list or o is g or 2 the next item in the list Order 0 ascending o descending o monotonically ascending or descending Sugih Jamin lamineecsumich edu Characteristics of Sorting Algorithms o internal vs external sorting whether the whole data set can be kept in main memory If only a block of data can be brought into memory at a time access between blocks becomes expensive o in place vs with auxiliary data structures don t forget the stack space used in recursive calls a by comparison or distribution based later a stable vs unstable sorting do multiple items containing the same key keep their relative ordering after the sort usually there is a secondary key whose ordering you want to keep eg last name first name stable sort is thus useful for sorting over multiple keys Sugih Jamin lamineecsumich edu Characteristics of Sorting Algorithms contd 0 direct vs indirect indirect ones modify pointersindices rather than the items themselves useful when it is expensive to move items 0 adaptive vs nonadaptive whether sequence of operations performed is a function of given input data Example bubblel is nonadaptive bubble2 that stops when array is sorted is adaptive Both are 0012 algorithms 0 simple vs complex complex ones usually run faster but unstable and harder to implement c worstcase vs expectedcase performance Sugih Jamin Gamineecsumich edu Sorting Algorithms Comparison based 0 selection sort straight selection sort heapsort o insertion sort insertion sort shell sort 0 merge sort 0 exchange sort bubble sort quick sort Distribution based counting sort radix sort bucket sort Sugih Jamin Gamineecsumich edu Selection Sort Elements added to the sorted sequence in order Algorithm see Fig 155 0 given a pile of items in an array 0 find the smallest largest item in array swap with first last position 0 find the second smallest largest item in array swap with second second last position 0 nonadaptive version continue until end of array 0 adaptive version don t swap if item is already in correct position Straight selection sort performs a linear search for the next smallest largest item Running time Sugih Jamin iamineecsumich edu Selection Sort Sort array a5 8 2 5 3 1 Nonadaptive Adaptive void void ssortnaint a int N ssortaint a int N Is it stable Is it stable Sugih Jamin Gamineecsumich edu Heapsort Use a MaxHeap MinHeap to select the next largest smallest element First build unsorted sequence into a binary MaxHeap MinHeap MaxHeap property root must be larger than all children Since a heap is a complete binary tree 0 can be implemented as an array 0 sorting can be done in place Given an array of unsorted elements first heapify the array Sugih Jamin lamineecsumich edu Heapify Building a Heap Bottomup heapification visit tree postorder o heapify left child a heapify right child a heapify root node To heapify a tree when both children are already heapified percolate down root node repeatedly swap root node with max min of two children until both children are smaller larger than root node or root node has become a leaf Sugih Jamin lamineecsumich edu lnplace Heapsort Heapify Fig 157 Preiss 0 an n node complete binary tree has 712 leaf nodes 0 only need to percolate down elements at indices Ln2J to 1 bottom up Heapsort Fig 158 Preiss next extract the elements in order 0 max item is always at root index 1 o rightmost element is always at the last index 0 after removing the root move rightmost element to index 1 and percolate down 0 store max element at the now free rightmost slot Sugih Jamin iamineecsumich edu Heapsort Time Complexity Heapify phase 001 o percolate down is Oog n o inspecting Ln2J element is 001 o complexity appears to be On log n but is actually 0n Preiss Th 152 Heapsort phase On log n 0 must dequeue n elements 0 each dequeuemax takes Oog n Total time complexity is still On log n Sugih Jamin lamineecsumich edu Insertion Sort Algorithm see Fig 152 0 given a pile of items in an array 0 insert into an already sorted array one item at a time using linear search 0 nonadaptive version continues linear search till end of sorted array 0 adaptive version stops linear search once an insertion point has been found Contrast to selection sort 0 selection sort select item from pile in order add to the front end of sorted list a insertion sort pick next item from pile insert in order into sorted list Sugih Jamin lamineecsumich edu Insertion Sort Sort array a5 2 3 8 5 1 Nonadaptive Adaptive void void isortnaint a int N isortaint a int N Is it stable Is it stable Sugih Jamin Gamineecsumich edu