Talk:Complexity of algorithms

From Citizendium, the Citizens' Compendium
Jump to: navigation, search
This article is developing and not approved.
Main Article
Talk
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
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)