> For the complete documentation index, see [llms.txt](https://cs-notes.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-2/bubble-sort.md).

# Bubble Sort

[Bubble Sort](/algorithm-notes/outline/overview-2/bubble-sort.md#bubble-sort) is a simple yet straightforward swap sorting primitive and its principle is the same as what you might expect from a bubble surfacing up and down in the water.

## Pseudocode

A naive implementation would be as follow to bubble up the biggest number to the rightmost position in each run for computing the ascending sequence and bubble up the smallest number to the rightmost position in each run for computing the descending sequence:

```
BUBBLE_SORT(array)
  for i := 1 to length(array)
    for j := 1 to length(array) - i
      if array[j] > array[j+1]
        swap(array[j], array[j+1])
```

To improve upon that, a **sentinel** is introduced so as to resolve useless iterations and comparisons in partially sorted inputs:

```
BUBBLE_SORT(array)
  sentinel := 1
  for i := 1 to length(array)
    if sentinel = 1
     break
    for j := 1 to length(array) - i
      if array[j] > array[j+1]
        swap(array[j], array[j+1])
        sentinel := 0
```

## Algorithm Analysis

[bubble sort](/algorithm-notes/outline/overview-2/bubble-sort.md#bubble-sort) is elementary yet simple to evaluate; it yields a [best-case](/algorithm-notes/outline/asymptotic-analysis.md) scenario of Ο(n) for partially sorted arrays and [worst-case](/algorithm-notes/outline/asymptotic-analysis.md) of Ο(n2)