Talk:Complexity of algorithms

This pseudocode

Procedure: BubbleSort(List[])

...

   For i = 0 to List.Size-1
      For j = i+1 to List.Size-1

...

I don't think this works at all.

I would write the pseudo-code more like this:

Procedure: BubbleSort(List[])
Inputs: List[] - A list of numbers
Begin:
   Sorted=false
   Do until sorted
      SwapsDone=false
      For k = FirstElement to SecondToLastElement
         If List[k] > List[k+1], Then
            Swap List[k] and List[k+1]
            SwapsDone=true
         End If
      Next k
      If SwapsDone then Sorted=false else Sorted=true
   loop 

It's still quite easy to see the complexity is quadratic, since at least one element bubbles into place each turn, exactly one in the worst case.

Ragnar Schroder 15:40, 15 November 2007 (CST)