Selection, Bubble and Insertion Sort

What sorting means

Sorting means putting items in order: numbers from smallest to largest, words in alphabet order, or people by age. It is one of the most useful things you can do to data. Once an array is sorted, equal values sit next to each other, and the smallest and largest values are at the two ends. You can also search a sorted array by halving it again and again (Lesson 28).

In JavaScript you will almost always sort with arr.sort((a, b) => a - b). (Lesson 18 explains why the comparison function (a, b) => a - b is needed.) So why learn to sort by hand? The three simple sorts in this lesson teach three core moves: find the smallest item, swap neighbours, and insert an item into a sorted part. These moves appear inside many interview problems. They also make the O(n log n) sorts in the next two lessons easier to understand. (O(n²) means the work grows with n × n. O(n log n) is much smaller, so it is much faster.)

Stability: keeping ties in order

When two items compare as equal, a stable sort keeps them in the order that they had before sorting. This matters when you sort records (objects with several fields) by one field:

const students = [  { name: "Asha",  grade: "B" },  { name: "Ben",   grade: "A" },  { name: "Chen",  grade: "B" },  { name: "Dara",  grade: "A" },];students.sort((a, b) => a.grade.localeCompare(b.grade));console.log(students.map((s) => s.name).join(", "));// Ben, Dara, Asha, Chen   — A's first; within each grade, the original order is kept

Asha came before Chen and both have a B, so a stable sort keeps Asha first. JavaScript's sort has been guaranteed stable since 2019 (ES2019). There is one more property to know. An in-place sort rearranges the array itself and uses only O(1) extra memory (a fixed small amount that does not grow with n).

Selection sort

Selection sort is a sorting algorithm that repeatedly selects the smallest remaining item and puts it in its place. Idea: find the smallest item and put it first. Then find the smallest of the rest and put it second. Repeat until the array is sorted. (To swap two items means to exchange their positions.)

function selectionSort(arr) {  const n = arr.length;  for (let i = 0; i < n - 1; i++) {    let minIdx = i;    for (let j = i + 1; j < n; j++) {           // find the smallest in arr[i..]      if (arr[j] < arr[minIdx]) minIdx = j;    }    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];  // put it at position i  }  return arr;}console.log(selectionSort([5, 3, 8, 1, 4])); // [ 1, 3, 4, 5, 8 ]

The inner loop always scans the whole unsorted part. That is (n − 1) + (n − 2) + … + 1 ≈ n²/2 comparisons, even if the array is already sorted. So selection sort is O(n²) in every case. Its one advantage is that it makes at most n − 1 swaps. It is not stable. A swap over a long distance can move an item past an equal item.

Bubble sort and the early exit

Bubble sort is a sorting algorithm that repeatedly compares neighbours and swaps them when they are in the wrong order. Idea: walk through the array, compare each pair of neighbours, and swap any pair that is in the wrong order. After one full pass (one walk through the array), the largest value has “bubbled” to the end, like an air bubble rising in water. Repeat on the rest.

function bubbleSort(arr) {  const n = arr.length;  for (let pass = 0; pass < n - 1; pass++) {    let swapped = false;    for (let j = 0; j < n - 1 - pass; j++) {     // the last "pass" items are already in place      if (arr[j] > arr[j + 1]) {        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];        swapped = true;      }    }    if (!swapped) break;                         // no swaps: already sorted, stop early  }  return arr;}console.log(bubbleSort([5, 3, 8, 1, 4])); // [ 1, 3, 4, 5, 8 ]console.log(bubbleSort([1, 2, 3, 4, 5])); // [ 1, 2, 3, 4, 5 ]   one pass, then stop

In the worst case it is O(n²), like selection sort. But the swapped flag gives it an early exit. If a whole pass makes no swaps, the array is already sorted, so we stop. On an array that is already sorted, that is just one pass, so it takes O(n). Bubble sort is stable, because it swaps only neighbours that are strictly out of order (equal neighbours stay where they are).

Insertion sort

Insertion sort is a sorting algorithm that builds a sorted part one item at a time, by inserting each new item into its correct place. Idea: this is how most people sort playing cards in their hand. Keep a sorted part on the left. Take the next item (called the key) and slide it left past every bigger item until it reaches its place.

Traced: insertion sort on [5, 2, 4, 1]

▶const arr = [5, 2, 4, 1];2for (let i = 1; i < arr.length; i++) {3  const key = arr[i];4  let j = i - 1;5  while (j >= 0 && arr[j] > key) {6    arr[j + 1] = arr[j];7    j--;8  }9  arr[j + 1] = key;10}11console.log(arr);

Why insertion sort loves nearly sorted data

The while loop stops as soon as it finds an item that is not bigger than the key. If the array is already sorted, it stops at once every time. That is n − 1 comparisons in total, so O(n). If every item is only a few places from where it belongs, each key moves only a few places, so the total is still close to O(n). Only a reversed array forces every key all the way to the front, and that costs O(n²).

The three side by side

In the worst case all three are O(n²). So none of them can sort 100,000 items in time (Lesson 12). For that you need the O(n log n) sorts: merge sort and quick sort.

Practice questions

These questions use the moves of the simple sorts. They do not ask you to sort a whole array. Say the time complexity of each answer.

function insertSorted(arr, x) {  let j = arr.length - 1;  arr.push(x);                         // make room (this slot is overwritten when needed)  while (j >= 0 && arr[j] > x) {    arr[j + 1] = arr[j];    j--;  }  arr[j + 1] = x;  return arr;}console.log(insertSorted([1, 3, 5, 8], 4)); // [ 1, 3, 4, 5, 8 ]console.log(insertSorted([2, 6], 9));       // [ 2, 6, 9 ]console.log(insertSorted([], 7));           // [ 7 ]

function insertSorted(arr, x) {  let i = 0;  while (i < arr.length && arr[i] <= x) i++;  arr.splice(i, 0, x);  return arr;}console.log(insertSorted([1, 3, 5, 8], 4)); // [ 1, 3, 4, 5, 8 ]

function heightChecker(heights) {  const expected = [...heights].sort((a, b) => a - b);  let count = 0;  for (let i = 0; i < heights.length; i++) {    if (heights[i] !== expected[i]) count++;  }  return count;}console.log(heightChecker([1, 1, 4, 2, 1, 3])); // 3console.log(heightChecker([5, 1, 2, 3, 4]));    // 5

function heightChecker(heights) {  const count = new Array(101).fill(0);  for (const h of heights) count[h]++;  let mismatches = 0;  let h = 1;  for (const actual of heights) {    while (count[h] === 0) h++;        // next height in sorted order    if (actual !== h) mismatches++;    count[h]--;  }  return mismatches;}console.log(heightChecker([1, 1, 4, 2, 1, 3])); // 3console.log(heightChecker([1, 2, 3]));          // 0

function kSmallest(nums, k) {  const a = [...nums];  for (let i = 0; i < k; i++) {    let minIdx = i;    for (let j = i + 1; j < a.length; j++) {      if (a[j] < a[minIdx]) minIdx = j;    }    [a[i], a[minIdx]] = [a[minIdx], a[i]];  }  return a.slice(0, k);}console.log(kSmallest([7, 2, 9, 4, 1], 2)); // [ 1, 2 ]console.log(kSmallest([3, 3, 1], 3));       // [ 1, 3, 3 ]

function kSmallest(nums, k) {  return [...nums].sort((a, b) => a - b).slice(0, k);}console.log(kSmallest([7, 2, 9, 4, 1], 2)); // [ 1, 2 ]

function bubbleSwaps(nums) {  const a = [...nums];  let swaps = 0;  for (let pass = 0; pass < a.length - 1; pass++) {    for (let j = 0; j < a.length - 1 - pass; j++) {      if (a[j] > a[j + 1]) {        [a[j], a[j + 1]] = [a[j + 1], a[j]];        swaps++;      }    }  }  return swaps;}console.log(bubbleSwaps([3, 1, 2]));       // 2console.log(bubbleSwaps([5, 3, 8, 1, 4])); // 6

function bubbleSwaps(nums) {  let inversions = 0;  for (let i = 0; i < nums.length; i++) {    for (let j = i + 1; j < nums.length; j++) {      if (nums[i] > nums[j]) inversions++;    }  }  return inversions;}console.log(bubbleSwaps([3, 1, 2]));       // 2console.log(bubbleSwaps([5, 3, 8, 1, 4])); // 6console.log(bubbleSwaps([1, 2, 3]));       // 0

function insertionSort(arr, cmp) {  for (let i = 1; i < arr.length; i++) {    const key = arr[i];    let j = i - 1;    while (j >= 0 && cmp(arr[j], key) > 0) {   // strictly greater: equal items never pass each other      arr[j + 1] = arr[j];      j--;    }    arr[j + 1] = key;  }  return arr;}const students = [  { name: "Asha", grade: "B" },  { name: "Ben", grade: "A" },  { name: "Chen", grade: "B" },  { name: "Dara", grade: "A" },];insertionSort(students, (a, b) => a.grade.localeCompare(b.grade));console.log(students.map((s) => s.name).join(", ")); // Ben, Dara, Asha, Chen

function sortArray(nums) {  for (let i = 1; i < nums.length; i++) {    const key = nums[i];    let j = i - 1;    while (j >= 0 && nums[j] > key) {      nums[j + 1] = nums[j];      j--;    }    nums[j + 1] = key;  }  return nums;}console.log(sortArray([5, 2, 3, 1])); // [ 1, 2, 3, 5 ]

function sortArray(nums) {  const OFFSET = 50000;  const count = new Array(100001).fill(0);  for (const x of nums) count[x + OFFSET]++;  let i = 0;  for (let v = 0; v < count.length; v++) {    while (count[v]-- > 0) nums[i++] = v - OFFSET;  }  return nums;}console.log(sortArray([5, 2, 3, 1]));       // [ 1, 2, 3, 5 ]console.log(sortArray([5, 1, 1, 2, 0, 0])); // [ 0, 0, 1, 1, 2, 5 ]console.log(sortArray([-3, 4, -50000]));    // [ -50000, -3, 4 ]

function sortArray(nums) {  return nums.sort((a, b) => a - b);}console.log(sortArray([5, 1, 1, 2, 0, 0])); // [ 0, 0, 1, 1, 2, 5 ]

Make it stick

What's next

Lesson 17 uses recursion from Lesson 14 to sort much faster. Split the array in half, sort each half, and merge the two sorted halves into one. This is merge sort, and it is O(n log n) in every case.