CITIDEL >
Planet Math Computer Science >
Planet Math Computer Science Collection >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10117/1210

Title:  lower bound for sorting 
Issue Date:  9May2006 
Publisher:  PlanetMath 
Citation:  http://planetmath.org/encyclopedia/LowerBoundForSorting.html 
Abstract:  Several wellknown sorting algorithms have average or worstcase running times of ... (heapsort, quicksort). One might ask: is it possible to do better? The answer to this question is ... no , at least for comparisonbased sorting algorithms. To prove this, we must prove that no algorithm can perform better (even algorithms that we do not know!). Often this sort of proof is intractable, but for comparisonbased sorting algorithms we can construct a model that corresponds to the entire class of algorithms. The model that we will use for this proof is a decision tree. The root of the decision tree corresponds to the state of the input of the sorting problem (e.g. an unsorted sequence of values). Each internal node of the decision tree represents such a state, as well as two possible decisions that can be made as a result of examining that state, leading to two new states. The leaf nodes are the final states of the algorithm, which in this case correspond to states where the input list is determined to be sorted. The worstcase running time of an algorithm modelled by a decision tree is the height or depth of that tree. A sorting algorithm can be thought of as generating some permutation of its input. Since the input can be in any order, every permutation is a possible output. In order for a sorting algorithm to be correct in the general case, it must be possible for that algorithm to generate every possible output. Therefore, in the decision tree representing such an algorithm, there must be one leaf for every one of ... permutations of 
URI:  http://www.citidel.org/handle/10117/1210 
Appears in Collections:  Planet Math Computer Science Collection

Files in This Item:
File 
Size  Format 
LowerBoundForSorting.html  25Kb  HTML  View/Open 

All items in DSpace are protected by copyright, with all rights reserved.
