algorithm

Bubble sort

   
Data structure Array
Worst-case performance О(n²) comparisons, О(n²) swaps
Best-case performance О(n) comparisons, О(1) swaps
Average performance О(n²) comparisons, О(n²) swaps
Worst-case space complexity O(1) auxiliary

A bubble sort, a sorting algorithm that continuously steps through a list, swapping items until they appear in the correct order. The list was plotted in a Cartesian coordinate system, with each point (x, y) indicating that the value y is stored at index x. Then the list would be sorted by bubble sort according to every pixel’s value. Note that the largest end gets sorted first, with smaller elements taking longer to move to their correct positions.

img

An example of bubble sort. Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

img

Implementations

Language Source
bubble_sort.c
bubble_sort.cpp
BubbleSort.java
bubble_sort.py
bubble_sort.js
bubble_sort.sh
bubble_sort.php
bubble_sort.rb
bubble_sort.swift
bubble_sort.go