Talk:Complexity of algorithms: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Subpagination Bot
m (Add {{subpages}} and remove checklist (details))
imported>Ragnar Schroder
No edit summary
 
Line 1: Line 1:
{{subpages}}
{{subpages}}
==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.
[[User:Ragnar Schroder|Ragnar Schroder]] 15:40, 15 November 2007 (CST)

Latest revision as of 15: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"