# MIT 6 046J - Lecture Notes (47 pages)

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

# Lecture Notes

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

View Full Document
View Full Document

## Lecture Notes

18 views

Pages:
47
School:
Massachusetts Institute of Technology
Course:
6 046j - Introduction to Algorithms
##### Introduction to Algorithms Documents
• 5 pages

• 13 pages

• 23 pages

• 54 pages

• 47 pages

• 30 pages

• 15 pages

• 2 pages

• 23 pages

• 6 pages

• 6 pages

• 2 pages

• 7 pages

• 29 pages

• 42 pages

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

Unlocking...