Bubble Sort

  • We go through the input sequence looking for inversions. For each inversion, we swap the two elements to put them in order. This way, larger elements bubble up and smaller elements bubble down.

  • When we go through the input sequence without making a single swap (and find that the sequence doesn’t have any more inversions), we stop.



bubbleSort(A, n):
    swapped = true
    while not swapped:
        swapped = false
        for i = 0 ... n - 2:
            if A[i] > A[i + 1]:
                swap A[i] and A[i + 1]
                swapped = true


  • In the best case, bubble sort takes Θ(N)\Theta(N) time.

  • In the worst case, Θ(N2)\Theta(N^2) time.


results matching ""

    No results matching ""