X hits on this document

Powerpoint document

Lower Bounds & Sorting in Linear Time - page 3 / 28

85 views

0 shares

0 downloads

0 comments

3 / 28

Comp 122

linsort - 3

Lin / Devi

Comp 122

Decision Tree

Binary-tree abstraction for any comparison sort.

Represents comparisons made by

»

a specific sorting algorithm

»

on inputs of a given size.

Abstracts away everything else – control and data movement – counting only comparisons.

Each internal node is annotated by i:j, which are indices of array elements from their original positions.

Each leaf is annotated by a permutation (1), (2), …, (n) of orders that the algorithm determines.

Document info
Document views85
Page views85
Page last viewedTue Jan 17 15:06:53 UTC 2017
Pages28
Paragraphs427
Words1924

Comments