Talk:Complexity of algorithms

From Citizendium, the Citizens' Compendium
Jump to: navigation, search
This article is developing and not approved.
Main Article
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
To learn how to fill out this checklist, please see CZ:The Article Checklist. To update this checklist edit the metadata template.
 Definition How fast the execution time (or memory usage) increases as the data set to be processed grows. [d] [e]

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
   Do until sorted
      For k = FirstElement to SecondToLastElement
         If List[k] > List[k+1], Then
            Swap List[k] and List[k+1]
         End If
      Next k
      If SwapsDone then Sorted=false else Sorted=true

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)