In-place sort

Selection Sort

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.

Quick Sort

DSA · Sorting

syntax

Pick a pivot. Partition: elements < pivot go left, >= pivot go right.
Recursively sort left and right partitions.

example

// JavaScript
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const pivotIdx = partition(arr, lo, hi);
  quickSort(arr, lo, pivotIdx - 1);
  quickSort(arr, pivotIdx + 1, hi);
  return arr;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

# Python
def quick_sort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return arr
    pivot_idx = partition(arr, lo, hi)
    quick_sort(arr, lo, pivot_idx - 1)
    quick_sort(arr, pivot_idx + 1, hi)
    return arr

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

output

quick_sort([10,7,8,9,1,5]) → [1,5,7,8,9,10]

Note Time: O(n log n) avg, O(n^2) worst (already sorted with bad pivot). Space: O(log n) avg stack. NOT stable. Randomizing the pivot avoids worst case. In practice, quicksort is often faster than merge sort due to cache locality. Lomuto partition (shown) is simpler; Hoare partition is faster.

DSAInterview Prep