Talk:Complexity of algorithms

From Citizendium
Jump to navigation Jump to search
This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
To learn how to update the categories for this article, see here. To update categories, edit the metadata template.
 Definition How fast the execution time (or memory usage) increases as the data set to be processed grows. [d] [e]
Checklist and Archives
 Workgroup categories Computers and Mathematics [Categories OK]
 Talk Archive none  English language variant British English

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)