MIT 6 046J - Lecture Notes (47 pages)

Previewing pages 1, 2, 3, 22, 23, 24, 45, 46, 47 of 47 page document View the full content.
View Full Document

Lecture Notes



Previewing pages 1, 2, 3, 22, 23, 24, 45, 46, 47 of actual document.

View the full content.
View Full Document
View Full Document

Lecture Notes

18 views


Pages:
47
School:
Massachusetts Institute of Technology
Course:
6 046j - Introduction to Algorithms

Unformatted text preview:

Introduction to Algorithms 6 046J 18 401J LECTURE 5 Sorting Lower Bounds Decision trees Linear Time Sorting Counting sort Radix sort Appendix Punched cards Prof Erik Demaine September 26 2005 Copyright 2001 5 Erik D Demaine and Charles E Leiserson L5 1 How fast can we sort All the sorting algorithms we have seen so far are comparison sorts only use comparisons to determine the relative order of elements E g insertion sort merge sort quicksort heapsort The best worst case running time that we ve seen for comparison sorting is O n lg n Is O n lg n the best we can do Decision trees can help us answer this question September 26 2005 Copyright 2001 5 Erik D Demaine and Charles E Leiserson L5 2 Decision tree example Sort a1 a2 an 1 2 1 2 2 3 2 3 123 123 1 3 1 3 213 213 1 3 1 3 132 132 312 312 2 3 2 3 231 231 321 321 Each internal node is labeled i j for i j 1 2 n The left subtree shows subsequent comparisons if ai aj The right subtree shows subsequent comparisons if ai aj September 26 2005 Copyright 2001 5 Erik D Demaine and Charles E Leiserson L5 3 Decision tree example Sort a1 a2 a3 9 4 6 1 2 1 2 9 4 2 3 2 3 123 123 1 3 1 3 213 213 1 3 1 3 132 132 312 312 2 3 2 3 231 231 321 321 Each internal node is labeled i j for i j 1 2 n The left subtree shows subsequent comparisons if ai aj The right subtree shows subsequent comparisons if ai aj September 26 2005 Copyright 2001 5 Erik D Demaine and Charles E Leiserson L5 4 Decision tree example Sort a1 a2 a3 9 4 6 1 2 1 2 2 3 2 3 123 123 1 3 1 3 213 213 1 3 1 3 132 132 312 312 9 6 2 3 2 3 231 231 321 321 Each internal node is labeled i j for i j 1 2 n The left subtree shows subsequent comparisons if ai aj The right subtree shows subsequent comparisons if ai aj September 26 2005 Copyright 2001 5 Erik D Demaine and Charles E Leiserson L5 5 Decision tree example Sort a1 a2 a3 9 4 6 1 2 1 2 2 3 2 3 123 123 1 3 1 3 213 213 4 6 2 3 2 3 1 3 1 3 132 132 312 312 231 231 321 321 Each internal node is labeled i j for i j 1 2 n The left



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?