i = 0
while i < n
  j = i + 1
  while j < n
    if a[i] > a[j]
      std::swap(a[i], a[j])
    j++
  i++
vec.size() with lst.size().
  | i = 0 while i < n j = i + 1 while j < n if a[i] > a[j] std::swap(a[i], a[j]) j++ i++ | O(1) while i < n O(1) while j < n if a[i] > a[j] O(1) O(1) O(1) | 
if statementif b s1 else s2
s1 or s2, but which one?
  b's cost.
  if Example| O(1)
while i < n
  O(1)
  while j < n
    if a[i] > a[j]
      O(1)
    O(1)
  O(1) | O(1)
while i < n
  O(1)
  while j < n
    O(1) + O(1) = O(1)
    O(1)
  O(1) | 
s1 ; s2
s1 is O(f), s2 is O(g), so s1; s2 is
O(f) + O(g) 
| O(1)
while i < n
  O(1)
  while j < n
    O(1)
    O(1)
  O(1) | O(1)
while i < n
  O(1)
  while j < n
    O(1) + O(1) = O(max(1, 1)) = O(1)
  O(1) | 
while b do s
s has asymptotic estimate O(f).
s gets executed some number of times.
  | O(1) while i < n O(1) while j < n O(1) O(1) | O(1)
while i < n
  O(1)
  O(n)*(O(1) + O(1)) = O(n)
  O(1) | 
| O(1) while i < n O(1) O(n) O(1) | O(1)
while i < n
  O(1) + O(n) + O(1) = O(n) | 
| O(1) while i < n O(n) | O(1)
O(n)*O(n) = O(n2)
 | 
| O(1) O(n2) | O(1) + O(n2) = O(n2) | 
In the worst case, swap sort moves O(n2) elements when sorting an n-element array.
while vec.size() > 0 vec.erase(vec.end() - 1) while vec.size() > 0 vec.erase(vec.begin())
| This page last modified on 2010 September 4. |