Bubble Sort

Definition

Definition

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted

Explanation

The Bubble Sort algorithm begins by iterating through the list from the start. It compares adjacent elements, swapping them if they're in the wrong order. This comparison continues for each pair until the end of the list is reached. This process repeats for every element until the entire list is sorted

Guidance

• Start from the beginning of the list
• Compare the first two elements
  • If the first element is greater than the second, swap them
  • Move to the next pair of elements
  • Repeat steps until you reach the end of the list
• Repeat steps until the entire list is sorted

Tips

• keep track of whether any swaps are made in each pass. If no swaps are made, the list is already sorted, and the algorithm can terminate early
• optimize the algorithm by implementing a flag to check if any swapping occurred in a pass. If no swaps occur, the list is sorted, and further iterations can be skipped

Practice

Practice

function bubbleSort(arr)
  n = length(arr)
  swapped = true
  while swapped is true
    swapped = false
    for i from 0 to n-2
      if arr[i] > arr[i+1]
        swap(arr[i], arr[i+1])
        swapped = true

Solution

package main

func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

public class BubbleSort {

  public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }
}

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
}

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        for j in 0..n - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

function bubbleSort(arr: number[]): void {
  const n: number = arr.length;
  for (let i: number = 0; i < n - 1; i++) {
    for (let j: number = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
}