Bubble sort
  • Best Case, O(n)
  • Worst Case, Ω(n^2)
  • Memory Complexity, O(1)
    1. #!/usr/bin/python
    2.  
    3. import random
    4.  
    5. def bubble_sort(l):
    6.     n = len(l)
    7.  
    8.     for i in range(n):
    9.         for j in range(n-i-1):
    10.             if l[j] > l[j+1]:
    11.                 l[j], l[j+1] = l[j+1], l[j]
    12.  
    13. def get_list():
    14.     random.seed()
    15.  
    16.     l = []
    17.     for i in range(10):
    18.         l.append(random.choice(range(10)))
    19.  
    20.     return l
    21.  
    22. def main():
    23.     l = get_list()
    24.     print(l)
    25.  
    26.     bubble_sort(l)
    27.     print(l)
    28.  
    29. if __name__ == '__main__':
    30.     main()
    31.
    Reach Best Case with Control
    1. #!/usr/bin/python
    2.  
    3. import random
    4.  
    5. def bubble_sort(l):
    6.     n = len(l)
    7.  
    8.     for i in range(n):
    9.         swap = False
    10.         for j in range(n-i-1):
    11.             if l[j] > l[j+1]:
    12.                 l[j], l[j+1] = l[j+1], l[j]
    13.                 swap = True
    14.         if not swap:
    15.             break
    16.  
    17. def get_list():
    18.     random.seed()
    19.  
    20.     l = []
    21.     for i in range(10):
    22.         l.append(random.choice(range(10)))
    23.  
    24.     return l
    25.  
    26. def main():
    27.     l = get_list()
    28.     print(l)
    29.  
    30.     bubble_sort(l)
    31.     print(l)
    32.  
    33. if __name__ == '__main__':
    34.     main()
    35.
    Reference
  • why is the time complexity of bubble sort's best case being O(n)