CIS-3050 Algorithms and Data Structures

Assignment 5

Due:  Monday, Nov. 15


Given the pseudocode for the three sorts we discussed in class (Bubble Sort, Selection Sort and Insertion Sort), answer the following for each sort.  Assume that the sorts will sort the given data from smallest to largest.

  1. What will the behavior of the sort be (including the asymptotic running time if you can determine it) if the data is ordered?  For example:
                    { 1, 2, 3, 4, 5, 6, 7, 8, 9 }


  1. What will the behavior of the sort be (including the asymptotic running time if you can determine it) if the data is in reverse order?  For example:
                    { 9, 8, 7, 6, 5, 4, 3, 2, 1 }



  1. What will the behavior of the sort be (including the asymptotic running time if you can determine it) if the data is as follows (largest element first)?
                    { 9, 1, 2, 3, 4, 5, 6, 7, 8 }


  1. What will the behavior of the sort be (including the asymptotic running time if you can determine it) if the data is as follows (smallest element last)?
                    {  2, 3, 4, 5, 6, 7, 8,  9, 1 }

For each of the 4 patterns above -- is there a clear winner amongst these algorthims in terms of sorting the pattern?   Why?  (This why may be very brief, in referring to your more complete description of the behavior of the sort.


In all cases, be sure to give a complete answer.  Some supporting evidence that might be useful would include the number of passes necessary over the data, the behavior of the algorithm with specific key values, and pictures or diagrams of intermediate positions of the elements. Your description should fully justify your given asymptotic running time.   However, it is not necessary to fully diagram every swap and every comparison -- just provide enough detail to justify your response about the ultimate performance of the sort.

The example data is just that -- an example.  If it is easier to explain with alternate data (or less data), you may.   There is no need to implement these sorts in code.