Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • How quick is bubble sort?

      3 June, 2021

      We said in the main article that in the worst case bubble sort will need n(n−1)2 steps to sort a list of n things. Here's a proof.

      Let's assume that the things we are sorting are numbers and that they need to be put in ascending order. On the first run through the list the algorithm has to compare the first and second number, then the second and third, then the third and fourth, and so on. For n numbers that's a total of n−1 comparisons (and potential swaps). Since we are looking at the worst case scenario we have to assume the list is not yet sorted, so a second iteration is needed. However, the first iteration will have made sure that the largest number in your list, call it x, will have moved to the end of the list. That's because the comparison involving x and the number that comes after it will have resulted in a swap moving x one place to the right (since x is largest of the list and therefore also larger than its right-hand neighbour). The next comparison will then also involve x together with its new right-hand neighbour, and also result in a swap moving x one place to the right. Continuing like this, you see that x eventually moves to the end of the list in one iteration. (If the largest number x appears several times in the list, then this argument works a little differently, but the result is still the same: the last number in the list after the first iteration will be x.) The fact that the largest number x is in its correct place (at the end of the list) means that on the second iteration of the algorithm we can ignore this last number. This means that on the second iteration the algorithm has to compare consecutive numbers in a list of n−1 numbers, giving a total of n−2 comparisons (and potential swaps) for the second iteration. Since we are looking at the worst case scenario we have to assume the list is not yet sorted, so a third iteration is needed. By the same reasoning as in the previous paragraphs, on the third iteration the algorithm will need to make n−3 comparisons (and potential swaps). Carrying on like this, we see that in the worst case scenario the algorithm will need a total of (n−1)+(n−2)+(n−3)+...+1 steps.

      From the formula for the summation of integers (see here) we know that

      (n−1)+(n−2)+(n−3)+...+1=n(n−1)/2. This proves the result.

      Back to the main article

      • Log in or register to post comments
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms