Talk:Complexity of algorithms
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)