Sorting algorithm

2 snippets in Interview Prep

DSAInterview Prep

Bubble Sort

syntax

Repeatedly swap adjacent elements if out of order.
After each pass, the largest unsorted element 'bubbles' to its correct position.

example

// JavaScript
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted
  }
  return arr;
}

# Python
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

output

bubble_sort([5,3,8,1,2]) → [1,2,3,5,8]

Note Time: O(n^2) average/worst, O(n) best (already sorted with early exit). Space: O(1). Stable sort. Never use in production — only know it for interviews. The early termination optimization (swapped flag) is worth mentioning.

Selection Sort

DSA · Sorting

syntax

Find the minimum element in the unsorted portion.
Swap it to the front of the unsorted portion.
Repeat.

example

// JavaScript
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

# Python
def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

output

selection_sort([64,25,12,22,11]) → [11,12,22,25,64]

Note Time: O(n^2) all cases. Space: O(1). NOT stable (swapping can change relative order of equal elements). Minimizes the number of swaps (at most n-1), which can matter when writes are expensive.