Homework 2, Sort of working on things.

Or working on sort things.

Short Description:

Goals

• Analyzed two algorithms in the manner required for the class.
• Refreshed your knowledge of two sorting algorithms.

Formal Description

1. Trace the algorithm for several different inputs.
2. Provide a high level description of the operation of the algorithm.
3. Provide an argument that the algorithm is correct and will produce an ordered array.
4. Discuss the worst, best, and average case input for this algorithm
5. Provide an analyses of the performance of the algorithm.

• Bubble(A)
     Input: an array A, with comparison operator < on the elements and size  0 ≤ A.size() 
     Output: A ordered by the < operator, smallest element first.
  
   n ← A.size()-1
   repeat
     swapped ← false
     for i ← 1 to n do
        if A[i-i] > A[i]
           Swap(A[i-1],A[i])
           swapped ← true
     n ← n - 1 
   until not swapped
  

• Insertion(A)
     Input: an array A, with comparison operator < on the elements and size  0 ≤ A.size() 
     Output: A ordered by the < operator, smallest element first.
  
    i ← 1
   while i < A.size()
      j ← i
      while j > 0 and A[j-1] > A[j]
        Swap(A[j], A[j-1])
        j ← j - 1
      i ← i + 1
  

Required Files

Submission