Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order (ascending or descending arrangement). The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Algorithm Visualization

Complexity

Name Best Average Worst Memory Stable Comments
Bubble sort $n$ $n^2$ $n^2$ $1$ Yes  

References

Implementations

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    from random import randint

N = 15
MIN = 1
MAX = 20

def BubbleSort(start:int, end:int, array:list):
    newEnd:int = start;
    for i in range(start, end):
        if array[i] > array[i + 1]:
            array[i], array[i+1] = array[i + 1], array[i]
            newEnd = i

    if newEnd == start:
        return
    else:
        BubbleSort(start, newEnd, array)

if __name__ == '__main__':
    array = [randint(MIN, MAX) for _ in range(N)]
    print("Initial Array: ", *array)
    BubbleSort(0, N-1, array)
    print("Sorted Array: ",*array)

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

    #include "algorithm-visualizer.h"

#define N   15
#define MIN 1
#define MAX 20

void BubbleSort(int start, int end, int array[]);

ChartTracer chartTracer("Chart");

int main() {
    int array[N];
    Randomize::Array1D<int>(N, *(new Randomize::Integer(MIN, MAX))).fill(&array[0]);
    chartTracer.set(array);
    Layout::setRoot(VerticalLayout({ chartTracer }));

    BubbleSort(0, N - 1, array);

    return 0;
}

void BubbleSort(int start, int end, int array[])
{
    chartTracer.select(end);

    int newEnd = start;
    for(int i = start; i < end; ++i)
    {
        chartTracer.select(i);
        chartTracer.select(i + 1);
        Tracer::delay();
        if(array[i] > array[i + 1])
        {
            std::swap(array[i], array[i + 1]);
            chartTracer.patch(i, array[i]);
            chartTracer.patch(i + 1, array[i + 1]);
            Tracer::delay();
            chartTracer.depatch(i);
            chartTracer.depatch(i + 1);
            newEnd = i;
        }

        chartTracer.deselect(i);
        chartTracer.deselect(i + 1);
    }

    if(newEnd == start)
    {
        return;
    }
    else
    {
        BubbleSort(start, newEnd, array);
    }
}

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

    import org.algorithm_visualizer.*;

import java.util.Arrays;

public class Main {

    private static ChartTracer chartTracer = new ChartTracer();

    private static LogTracer logTracer = new LogTracer("Console");

    private static Integer [] array = (Integer[]) new Randomize.Array1D(15, new Randomize.Integer(1, 20)).create();

    public static void main(String[] args) {

        int length = array.length;

        logTracer.printf("original array = %s\n",Arrays.toString(array));
        chartTracer.set(array);
        Layout.setRoot(new VerticalLayout(new Commander[]{chartTracer, logTracer}));
        Tracer.delay();

        boolean flag;

        for (int i = length - 1; i > 0; i--) {
            flag = true;
            for (int j = 0; j < i; j++) {
                chartTracer.select(j);
                chartTracer.select(j + 1);
                Tracer.delay();
                if (array[j] > array[j + 1]) {
                    logTracer.printf("swap %s and %s\n",array[j],array[j + 1]);
                    swap(j, j + 1, array);
                    flag = false;
                }
                chartTracer.deselect(j);
                chartTracer.deselect(j + 1);
            }
            if (flag) {
                break;
            }
        }


        logTracer.printf("sorted array = %s\n",Arrays.toString(array));

    }

    private static void swap(int x, int y, Integer [] array) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
        chartTracer.patch(x, array[x]);
        chartTracer.patch(y, array[y]);
        Tracer.delay();
        chartTracer.depatch(x);
        chartTracer.depatch(y);
    }

}

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

    console.log(`original array = [${D.join(', ')}]`);

let N = D.length;
let swapped;
do {
  swapped = false;
  
  for (let i = 1; i < N; i++) {
    
    if (D[i - 1] > D[i]) {
      
      console.log(`swap ${D[i - 1]} and ${D[i]}`);
      
      const temp = D[i - 1];
      D[i - 1] = D[i];
      D[i] = temp;
      swapped = true;
      
    }
    
  }
  
  N--;
} while (swapped);

console.log(`sorted array = [${D.join(', ')}]`);