DOC PREVIEW
MIT 6 006 - Linear Bounds Linear-Time Sorting

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

MIT OpenCourseWare http://ocw.mit.edu6.006 Introduction to AlgorithmsSpring 2008For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.Lecture 10 Sorting III: Linear Bounds Linear-Time Sorting 6.006 Spring 2008 Lecture 10: Sorting III: Linear Bounds Linear-Time Sorting Lecture Overview • Sorting lower bounds – Decision Trees • Linear-Time Sorting – Counting Sort Readings CLRS 8.1-8.4 Comparison Sorting Insertion sort, merge sort and heap sort are all comparison sorts. The best worst case running time we know is O(n lg n). Can we do better? Decision-Tree Example Sort < a1, a2, an >.· · · 1:22:31:31:32:3231321312132123213Figure 1: Decision Tree Each internal node labeled i : j, compare ai and aj , go left if ai ≤ aj , go right otherwise. 1Lecture 10 Sorting III: Linear Bounds Linear-Time Sorting 6.006 Spring 2008 Example Sort < a1, a2, a3 >=< 9, 4, 6 > Each leaf contains a permutation, i.e., a total ordering. 1:32:32:32311:29 > 4 (a1 > a2)(a2 ≤ a3) 4 ≤ 69 > 6 (a1 > a3)4 ≤ 6 ≤ 9Figure 2: Decision Tree Execution Decision Tree Model Can model execution of any comparison sort. In order to sort, we need to generate a total ordering of elements. • One tree size for each input size n • Running time of algo: length of path taken • Worst-case running time: height of the tree Theorem Any decision tree that can sort n elements must have height Ω(n lg n). Proof: Tree must contain ≥ n! leaves since there are n! possible permutations. A height-h binary tree has ≤ 2h leaves. Thus, n! ≤ 2h n = ⇒ h ≥ lg(n!) (≥ lg((e )n) Stirling) ≥ n lg n − n lg e = Ω(n lg n) 2Lecture 10 Sorting III: Linear Bounds Linear-Time Sorting 6.006 Spring 2008 Sorting in Linear Time Counting Sort: no comparisons between elements Input: A[1 . . . n] where A[j] � {1, 2, , k} · · · Output: B[1 . . . n] sorted Auxiliary Storage: C[1 . . . k] Intuition Since elements are in the range {1, 2, , k}, imagine collecting all the j’s such that A[j] = 1, · · · then the j’s such that A[j] = 2, etc. Don’t compare elements, so it is not a comparison sort! A[j]’s index into appropriate positions. Pseudo Code and Analysis θ(k) θ(n) θ(k) θ(n) {for i ← 1 to kdo C [i] = 0{for j ← 1 to ndo C [A[j]] = C [A[j]] + 1{for i ← 2 to kdo C [i] = C [i] + C [i-1]{for j ← n downto 1do B[C [A[j]]] = A[j] C [A[j]] = C [A[j]] - 1θ(n+k) Figure 3: Counting Sort 3Lecture 10 Sorting III: Linear Bounds Linear-Time Sorting 6.006 Spring 2008 Example Note: Records may be associated with the A[i]’s. 143431 2 3 4 5313441 2 3 4 5 A:B:00001 2 3 4 C:0122C:11351 2 3 4 C:24Figure 4: Counting Sort Execution A[n] = A[5] = 3 C[3] = 3 B[3] = A[5] = 3, C[3] decr. A[4] = 4 C[4] = 5 B[5] = A[4] = 4, C[4] decr. and so on . . .


View Full Document

MIT 6 006 - Linear Bounds Linear-Time Sorting

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Linear Bounds Linear-Time Sorting
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Linear Bounds Linear-Time Sorting 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 Linear Bounds Linear-Time Sorting 2 2 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?