Talk:Complexity of algorithms: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>D. Matt Innis
m (Talk:Big O notation moved to Talk:Complexity of algorithms: per math author request and computer editor approval)
imported>Ragnar Schroder
No edit summary
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{checklist
{{subpages}}
|                abc = Big O notation (computer science)
 
|                cat1 = Computers
==This pseudocode==
|                cat2 = Mathematics
 
|                cat3 =  
Procedure: BubbleSort(List[])
|           cat_check = n
 
|             status = 2
...
|        underlinked = y
 
|            cleanup = n
    For i = 0 to List.Size-1
|                  by = --[[User:Aleksander Stos|AlekStos]] 14:48, 24 March 2007 (CDT)
      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.
 
[[User:Ragnar Schroder|Ragnar Schroder]] 15:40, 15 November 2007 (CST)

Latest revision as of 16:40, 15 November 2007

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)

Retrieved from "https://citizendium.org/wiki/index.php?title=Talk:Complexity_of_algorithms&oldid=20553"