Bubble Sort

When it comes to sorting algorithms, Bubble Sort is usually the first that comes to mind. Though it might not be the fastest tool in the shed, it's definitely straightforward to implement and is often the first sorting method new programmers think of when trying to implement a sorting method on their own.

Here's how it works: we go through each element in our vector and check to see if it is larger than the element to it's right. If it is, we swap the elements and then move to the next element. In this way, we sweep through the array times for each element and continually swap any two adjacent elements that are improperly ordered. This means that we need to go through the vector times with code similar to the following:

function bubble_sort(a::Vector{Float64})
    n = length(a)
    for i = 1:n
        for j = 1:n-1
            if(a[j] < a[j+1])
                a[j], a[j+1] = a[j+1], a[j]
            end
        end
    end
end
public static List<T> RunBubbleSort<T>(List<T> list) where T : IComparable<T>
{
    var length = list.Count;

    for (int i = 0; i < length; i++)
    {
        for (int j = 1; j < length; j++)
        {
            if (list[j - 1].CompareTo(list[j]) > 0)
            {
                var temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
            }
        }
    }

    return list;
}
void bubble_sort(int *array, size_t n) {
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n - 1; ++j) {
            if (array[j] > array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}
static void bubbleSort(int[] arr) {
    for (int r = arr.length - 1; r > 0; r--) {
        for (int i = 0; i < r; i++) {
            if(arr[i] > arr[i + 1]) {
                int tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
            }
        }
    }
}
function bubbleSort(arr) {
  for (let r = arr.length -1; r > 0; r--) {
    for (let i = 0; i < r; i++) {
      if (arr[i] > arr[i + 1]) {
        let tmp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
      }
    }
  }
}
def bubble_sort(array):
    len_array = len(array)
    for i in range(len_array):
        for j in range(len_array - i - 1):
            if(array[j] > array[j+1]):
                array[j], array[j+1] = array[j+1], array[j] #swap elements in the list
function sorted_array = bubble_sort(array)
    for i=1:length(array)
        for j=1:length(array)-i
            if array(j) > array(j+1)
                % swap elements in the list
                temp       = array(j);
                array(j)   = array(j+1);
                array(j+1) = temp;
            end
        end
    end
    sorted_array = array
end
bubbleSort :: (Ord a) => [a] -> [a]
bubbleSort x = (!!length x) $ iterate bubble x
  where bubble (x:y:r)
          | x <= y    = x : bubble (y:r)
          | otherwise = y : bubble (x:r)
        bubble x = x
template <class Iter>
void bubble_sort(Iter first, Iter last) {
  for (auto it1 = first; it1 != last; ++it1) {
    for (auto it2 = first; it2 + 1 != last; ++it2) {
      // these are unsorted! gotta swap 'em
      if (*(it2 + 1) < *it2) {
        std::iter_swap(it2, it2 + 1);
      }
    }
  }
}
fn bubble_sort(a: &mut [u32]) {
    let n = a.len();

    for _ in 0..n {
        for j in 1..n {
            if a[j - 1] > a[j] {
                a.swap(j, j - 1);
            }
        }
    }
}
void bubbleSort(R)(ref R range)
if (isRandomAccessRange!R && hasAssignableElements!R && hasLength!R)
{
    import std.algorithm : swap;

    foreach (i; 0 .. range.length) {
        bool isSorted = true;
        foreach (j; 0 .. range.length - 1)
            if (range[j + 1] < range[j]) {
                swap(range[j + 1], range[j]);
                isSorted = false;
            }
        if (isSorted)
            return;
    }
}
func bubbleSort(array []int) {
    n := len(array)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-i-1; j++ {
            if array[j] > array[j+1] {
                array[j], array[j+1] = array[j+1], array[j]
                swapped = true
            }
        }
        if !swapped {
            break
        }
    }
}
(define bubbleSort
  (case-lambda [(l) (bubbleSort l (length l))]
               [(l n) (if (= n 1)
                          l
                          (bubbleSort (pass l 0 n) (- n 1)))]))

; a single pass, if this is the nth pass, then we know that the (n - 1) last elements are already sorted
(define (pass l counter n)
  (let ([x (first l)]
        [y (second l)]
        [r (drop l 2)])
    (cond [(= (- n counter) 2) (cons (min x y) (cons (max x y) r))]
          [(cons (min x y) (pass  (cons (max x y) r) (+ counter 1) n))])))
func bubbleSort(sortArray: inout [Int]) -> [Int] {
    for i in (1..<sortArray.count).reversed() {
        for j in 0..<i {
            if sortArray[j] > sortArray[j+1] {
                let temp = sortArray[j]
                sortArray[j] = sortArray[j + 1]
                sortArray[j + 1] = temp
            }
        }
    }

    return sortArray
}
:"L IS LENGTH OF LIST"
:dim(L1)→L
:For(A,1,L)
:For(X,1,L-1)
:If L1(X)>L1(X+1)
:Then
:L1(X)→Y
:L1(X+1)→L1(X)
:Y→L1(X+1)
:End
:End
:End
def bubble_sort(arr)
    (0..arr.length - 1).each do
        (0..arr.length - 2).each do |k|
            if arr[k] > arr[k + 1]
                arr[k + 1], arr[k] = arr[k], arr[k + 1]
            end
        end
    end

    return arr
end
def bubble_sort(arr)
  arr = arr.dup 
  (0 ... arr.size).each do 
    (0 ... arr.size-1).each do |k| 
      if arr[k] > arr[k+1]
        arr[k+1],arr[k] = arr[k],arr[k+1]
      end
    end
  end 
  arr
end
function bubble_sort(array $arr): array
{
  for ($i = 0, $length = count($arr); $i < $length; $i++) {
    for ($j = 1; $j < $length; $j++) {
      if ($arr[$j - 1] > $arr[$j]) {
        $tmp = $arr[$j - 1];
        $arr[$j - 1] = $arr[$j];
        $arr[$j] = $tmp;
      }
    }
  }
  return $arr;
}

... And that's it for the simplest bubble sort method. Now, as you might imagine, computer scientists have optimized this to the fiery lakes of Michigan and back, so we'll come back to this in the future and talk about how to optimize it. For now, it's fine to just bask in the simplicity that is bubble sort. Trust me, there are plenty of more complicated algorithms that do precisely the same thing, only much, much better (for most cases).

Example Code

function bubble_sort(a::Vector{Float64})
    n = length(a)
    for i = 1:n
        for j = 1:n-1
            if(a[j] < a[j+1])
                a[j], a[j+1] = a[j+1], a[j]
            end
        end
    end
end


function main()
    a = [1., 3, 2, 4, 5, 10, 50, 7, 1.5, 0.3]
    bubble_sort(a)
    println(a)
end

main()

BubbleSort.cs

// submitted by Julian Schacher (jspp)
using System;
using System.Collections.Generic;

namespace BubbleSort
{
    public static class BubbleSort
    {
        public static List<T> RunBubbleSort<T>(List<T> list) where T : IComparable<T>
        {
            var length = list.Count;

            for (int i = 0; i < length; i++)
            {
                for (int j = 1; j < length; j++)
                {
                    if (list[j - 1].CompareTo(list[j]) > 0)
                    {
                        var temp = list[j - 1];
                        list[j - 1] = list[j];
                        list[j] = temp;
                    }
                }
            }

            return list;
        }
    }
}

Program.cs

// submitted by Julian Schacher (jspp)
using System;
using System.Collections.Generic;

namespace BubbleSort
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("BubbleSort");
            var listBubble = new List<int>() { 1, 2, 6, 4, 9, 54, 3, 2, 7, 15 };
            Console.Write("unsorted: ");
            foreach (var number in listBubble)
                Console.Write(number + " ");
            Console.WriteLine();
            listBubble = BubbleSort.RunBubbleSort(listBubble);
            Console.Write("sorted: ");
            foreach (var number in listBubble)
                Console.Write(number + " ");
            Console.WriteLine();
        }
    }
}
#include <stdio.h>

void print_range(int *array, size_t n) {
    for (size_t i = 0; i < n; ++i) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void bubble_sort(int *array, size_t n) {
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n - 1; ++j) {
            if (array[j] > array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}

int main() {
    int array[] = {1, 45, 756, 4569, 56, 3, 8, 5, -10, -4};
    size_t N = sizeof(array) / sizeof(*array);

    printf("Unsorted array:\n");
    print_range(array, N);

    bubble_sort(array, N);

    printf("\nSorted array:\n");
    print_range(array, N);

    return 0;
}
public class Bubble {
    static void bubbleSort(int[] arr) {
        for (int r = arr.length - 1; r > 0; r--) {
            for (int i = 0; i < r; i++) {
                if(arr[i] > arr[i + 1]) {
                    int tmp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = tmp;
                }
            }
        }
    }


    public static void main(String[] args) {
        int[] test = new int[]{20, -3, 50, 1, -6, 59};

        System.out.println("Unsorted array :");
        for (int i = 0; i < test.length; i++) {
            System.out.print(test[i] + " ");
        }

        bubbleSort(test);

        System.out.println("\n\nSorted array :");
        for (int i = 0; i < test.length; i++) {
            System.out.print(test[i] + " ");
        }
        System.out.println("");
    }
}
function bubbleSort(arr) {
  for (let r = arr.length -1; r > 0; r--) {
    for (let i = 0; i < r; i++) {
      if (arr[i] > arr[i + 1]) {
        let tmp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
      }
    }
  }
}
import random


def bubble_sort(array):
    len_array = len(array)
    for i in range(len_array):
        for j in range(len_array - i - 1):
            if(array[j] > array[j+1]):
                array[j], array[j+1] = array[j+1], array[j] #swap elements in the list

def main():
    number = [random.randint(0, 1000) for _ in range(10)]
    print("Before Sorting  {}".format(number))
    bubble_sort(number)
    print("After Sorting  {}".format(number))

main()
function main()
    array = floor( rand(1,7)*100 );
    disp('Before Sorting:')
    disp(array)

    array = bubble_sort(array);
    disp('After Sorting')
    disp(array)
end

function sorted_array = bubble_sort(array)
    for i=1:length(array)
        for j=1:length(array)-i
            if array(j) > array(j+1)
                % swap elements in the list
                temp       = array(j);
                array(j)   = array(j+1);
                array(j+1) = temp;
            end
        end
    end
    sorted_array = array
end
bubbleSort :: (Ord a) => [a] -> [a]
bubbleSort x = (!!length x) $ iterate bubble x
  where bubble (x:y:r)
          | x <= y    = x : bubble (y:r)
          | otherwise = y : bubble (x:r)
        bubble x = x
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>

template <class Iter>
void print_range(Iter first, Iter last) {
  for (auto it = first; it != last; ++it)
    std::cout << *it << " ";
  std::cout << std::endl;
}

template <class Iter>
void bubble_sort(Iter first, Iter last) {
  for (auto it1 = first; it1 != last; ++it1) {
    for (auto it2 = first; it2 + 1 != last; ++it2) {
      // these are unsorted! gotta swap 'em
      if (*(it2 + 1) < *it2) {
        std::iter_swap(it2, it2 + 1);
      }
    }
  }
}

int main() {
  int input[] = {1, 45, 756, 4569, 56, 3, 8, 5, -10, -4};

  std::cout << "Unsorted array:\n";
  print_range(std::begin(input), std::end(input));

  bubble_sort(std::begin(input), std::end(input));

  std::cout << "\nSorted array:\n";
  print_range(std::begin(input), std::end(input));
}
extern crate rand; // External crate that provides random number generation tools

use rand::{thread_rng, Rng}; // Used for random number generation
use rand::distributions::Uniform; // Used for a uniform distribution

fn bubble_sort(a: &mut [u32]) {
    let n = a.len();

    for _ in 0..n {
        for j in 1..n {
            if a[j - 1] > a[j] {
                a.swap(j, j - 1);
            }
        }
    }
}

fn main() {
    let mut rng = thread_rng(); // Create random number generator
    let num_range = Uniform::new_inclusive(0, 10000); // Obtain uniform distribution of range [0, 10000]
    let mut rand_vec: Vec<u32> = rng.sample_iter(&num_range).take(10).collect();
    // Generates random values over that range, take 10 values from it and collect in vector

    println!("Before sorting: {:?}", rand_vec);
    bubble_sort(&mut rand_vec);
    println!("After sorting: {:?}", rand_vec);
}
import std.range : hasAssignableElements, isRandomAccessRange, hasLength;

void bubbleSort(R)(ref R range)
if (isRandomAccessRange!R && hasAssignableElements!R && hasLength!R)
{
    import std.algorithm : swap;

    foreach (i; 0 .. range.length) {
        bool isSorted = true;
        foreach (j; 0 .. range.length - 1)
            if (range[j + 1] < range[j]) {
                swap(range[j + 1], range[j]);
                isSorted = false;
            }
        if (isSorted)
            return;
    }
}

void main() @safe
{
    import std.stdio : writefln;
    import std.range : generate, take;
    import std.array : array;
    import std.random : uniform01;

    auto input = generate!(() => uniform01!float).take(10).array;
    writefln!"before sorting:\n%s"(input);
    bubbleSort(input);
    writefln!"after sorting:\n%s"(input);
}
// Submitted by Chinmaya Mahesh (chin123)

package main

import "fmt"

func bubbleSort(array []int) {
    n := len(array)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-i-1; j++ {
            if array[j] > array[j+1] {
                array[j], array[j+1] = array[j+1], array[j]
                swapped = true
            }
        }
        if !swapped {
            break
        }
    }
}

func main() {
    array := [10]int{1, 45, 756, 4569, 56, 3, 8, 5, -10, -4}
    fmt.Println("Unsorted array:", array)

    bubbleSort(array[:])

    fmt.Println("Sorted array:", array)
}
#lang racket

(provide bubbleSort)


(define bubbleSort
  (case-lambda [(l) (bubbleSort l (length l))]
               [(l n) (if (= n 1)
                          l
                          (bubbleSort (pass l 0 n) (- n 1)))]))

; a single pass, if this is the nth pass, then we know that the (n - 1) last elements are already sorted
(define (pass l counter n)
  (let ([x (first l)]
        [y (second l)]
        [r (drop l 2)])
    (cond [(= (- n counter) 2) (cons (min x y) (cons (max x y) r))]
          [(cons (min x y) (pass  (cons (max x y) r) (+ counter 1) n))])))


((lambda (x) (display (bubbleSort x))) (read))
func bubbleSort(sortArray: inout [Int]) -> [Int] {
    for i in (1..<sortArray.count).reversed() {
        for j in 0..<i {
            if sortArray[j] > sortArray[j+1] {
                let temp = sortArray[j]
                sortArray[j] = sortArray[j + 1]
                sortArray[j + 1] = temp
            }
        }
    }

    return sortArray
}

func main() {
    var testArray = [4,5,123,759,-132,8940,24,34,-5]
    print(bubbleSort(sortArray: &testArray))
}

main()
:"SUBMITTED BY GIBUS WEARING BRONY"
:"L IS LENGTH OF LIST"
:dim(L1)→L
:For(A,1,L)
:For(X,1,L-1)
:If L1(X)>L1(X+1)
:Then
:L1(X)→Y
:L1(X+1)→L1(X)
:Y→L1(X+1)
:End
:End
:End
:Disp L1
#!/usr/bin/env ruby

def bubble_sort(arr)
    (0..arr.length - 1).each do
        (0..arr.length - 2).each do |k|
            if arr[k] > arr[k + 1]
                arr[k + 1], arr[k] = arr[k], arr[k + 1]
            end
        end
    end

    return arr
end

def main
    range = [200, 79, 69, 45, 32, 5, 15, 88, 620, 125]    
    puts "The range before sorting is #{range}"
    range = bubble_sort(range)
    puts "The range after sorting is #{range}"
end

main()
def bubble_sort(arr)
  arr = arr.dup 
  (0 ... arr.size).each do 
    (0 ... arr.size-1).each do |k| 
      if arr[k] > arr[k+1]
        arr[k+1],arr[k] = arr[k],arr[k+1]
      end
    end
  end 
  arr
end

def main 
  number = 10.times.map{rand(0..1_000)}.to_a 
  pp "The array before sorting is #{number}"
  number = bubble_sort number 
  pp "The array after  sorting is #{number}"
end 

main
<?php

function bubble_sort(array $arr): array
{
  for ($i = 0, $length = count($arr); $i < $length; $i++) {
    for ($j = 1; $j < $length; $j++) {
      if ($arr[$j - 1] > $arr[$j]) {
        $tmp = $arr[$j - 1];
        $arr[$j - 1] = $arr[$j];
        $arr[$j] = $tmp;
      }
    }
  }
  return $arr;
}

$unsorted = [1, 2, 6, 47, 4, 9, 3, 7, 8, 23, 15];
$bubble_sorted = bubble_sort($unsorted);

echo sprintf('Unsorted: %s%s', implode(',', $unsorted), PHP_EOL);
echo sprintf('Sorted: %s%s', implode(',', $bubble_sorted), PHP_EOL);

results matching ""

    No results matching ""