curInput.txt

6 9 is bigger than 6 so we go this way and then we compare the second element with the third element four is less than 6 and so we go this way and the claim is that this is the correct permutation of the elements you take a2 which is 4 then you take a3 which is 6 and then you take a1 which is 9 so indeed that works out and if i got if i wrote this down right this is a sorting algorithm in the decision tree model so in general let me just say the the rules of this game so in general we have n elements we want to sort and i only drew the n equals 3 case because they get these trees get very big very quickly each internal node so every non leaf node has a label of the form ij where i and j are between 1 and n and this means that we compare ai with aj and we have 2 subtrees from every such node we have the left subtree which tells you what the algorithm does what subsequent comparisons it makes if it comes out less than and we have to be a little bit careful because it could also come out equal so what well do is the left subtree corresponds to less than or equal to and the right subtree corresponds to strictly greater than so thats a little bit more precise than what we were doing here everything was all the elements are distinct so no problem but in general we care about the equality case too to be general so that was the internal nodes and then each leaf node gives you a permutation so in order to be the answer to the sorting problem that permutation better have the property that it orders the elements so this is from the first lecture when we defined the sorting problem some permutation on n things such that a pi of 1 is less than or equal to a pi of 2 and so on okay so thats the definition of a decision tree any tree any binary tree with these kinds of labels satisfies all these properties that is in some sense a sorting algorithm it is a sorting algorithm in the decision tree model now as you might expect this is a really not too different from the comparison model if i give you a comparison sorting algorithm we have these 4 quick sort heap sort merge sort insertion sort all of them can be translated into the decision tree model it is sort of a graphical representation of what the algorithm does its not a terribly useful 1 for writing down an algorithm any guesses why why do do we not draw these pictures as a definition of quick sort or a definition of merge sort it depends on the size of the input that is a good point so this tree is specific to the value of n so it is in some sense not as generic now we could try to write down a construction for an arbitrary value of n of one of these decision trees and that would give us sort of a real algorithm that works for any input but even then this is not a terribly convenient representation for writing down an algorithm okay well lets lets write down a transformation that converts a comparison sorting algorithm to a decision tree and then maybe you will see why this is not a useless model obviously i would not be telling you otherwise it will be very powerful for proving that we can not do better than n log n but as writing down an algorithm if you were going to implement something this tree is not so useful