1. Problems 71–80
Same format as the previous modules: expand a problem to see the approach and both
commented solutions. All six sorts use the same test input, [5, 2, 9, 1, 5, 6],
so you can compare how differently each one gets to the same answer.
P71
Bubble Sort
Repeatedly swap adjacent out-of-order pairs.
Bubble Sort
Repeatedly swap adjacent out-of-order pairs.
Approach: on each full pass, compare every adjacent pair and swap if they're out of order — the largest unsorted value "bubbles" to its correct position by the end of each pass, so each pass can check one element fewer than the last.
JavaScript
// Repeatedly swap adjacent out-of-order pairs; the largest unsorted value
// "bubbles" to the end on each full pass.
function bubbleSort(arr) {
const result = [...arr];
for (let i = 0; i < result.length - 1; i++) {
for (let j = 0; j < result.length - 1 - i; j++) {
if (result[j] > result[j + 1]) {
[result[j], result[j + 1]] = [result[j + 1], result[j]]; // swap
}
}
}
return result;
}
console.log(bubbleSort([5, 2, 9, 1, 5, 6])); // [1, 2, 5, 5, 6, 9]Python
def bubble_sort(items: list) -> list:
result = items[:]
n = len(result)
for i in range(n - 1):
for j in range(n - 1 - i):
if result[j] > result[j + 1]:
result[j], result[j + 1] = result[j + 1], result[j] # swap
return result
print(bubble_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9]
P72
Selection Sort
Find the minimum of the unsorted remainder, swap it into place.
Selection Sort
Find the minimum of the unsorted remainder, swap it into place.
Approach: scan the unsorted remainder for its smallest value, then swap that value into the next sorted position — one swap per pass, unlike bubble sort's many.
JavaScript
// Find the minimum of the unsorted remainder and swap it into place, one
// position at a time.
function selectionSort(arr) {
const result = [...arr];
for (let i = 0; i < result.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < result.length; j++) {
if (result[j] < result[minIndex]) minIndex = j; // track the smallest so far
}
if (minIndex !== i) {
[result[i], result[minIndex]] = [result[minIndex], result[i]];
}
}
return result;
}
console.log(selectionSort([5, 2, 9, 1, 5, 6])); // [1, 2, 5, 5, 6, 9]Python
def selection_sort(items: list) -> list:
result = items[:]
n = len(result)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if result[j] < result[min_index]:
min_index = j # track the smallest so far
if min_index != i:
result[i], result[min_index] = result[min_index], result[i]
return result
print(selection_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9]
P73
Insertion Sort
Grow a sorted region at the front, one element at a time.
Insertion Sort
Grow a sorted region at the front, one element at a time.
Approach: take the next unsorted element and slide it backward through the already-sorted region until it lands in the right spot — the same motion as sorting a hand of playing cards.
JavaScript
// Grow a sorted region at the front one element at a time, sliding each new
// element backward until it lands in the right spot.
function insertionSort(arr) {
const result = [...arr];
for (let i = 1; i < result.length; i++) {
const current = result[i];
let j = i - 1;
while (j >= 0 && result[j] > current) {
result[j + 1] = result[j]; // shift larger elements one step right
j--;
}
result[j + 1] = current; // drop it into the gap left behind
}
return result;
}
console.log(insertionSort([5, 2, 9, 1, 5, 6])); // [1, 2, 5, 5, 6, 9]Python
def insertion_sort(items: list) -> list:
result = items[:]
for i in range(1, len(result)):
current = result[i]
j = i - 1
while j >= 0 and result[j] > current:
result[j + 1] = result[j] # shift larger elements one step right
j -= 1
result[j + 1] = current # drop it into the gap left behind
return result
print(insertion_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9]
P74
Merge Sort
Split in half recursively, then merge sorted halves back together.
Merge Sort
Split in half recursively, then merge sorted halves back together.
Approach: split the list in half recursively down to single elements (always sorted on their own), then merge pairs of already-sorted halves back together — reusing the exact two-pointer merge from Module 3's "merge two sorted lists" problem.
JavaScript
// Split in half recursively down to single elements, then merge pairs of
// already-sorted halves back together (reusing Module 3's mergeSorted idea).
function mergeSort(arr) {
if (arr.length <= 1) return arr; // a list of 0 or 1 elements is already sorted
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(a, b) {
const merged = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
merged.push(a[i] <= b[j] ? a[i++] : b[j++]);
}
return merged.concat(a.slice(i)).concat(b.slice(j));
}
console.log(mergeSort([5, 2, 9, 1, 5, 6])); // [1, 2, 5, 5, 6, 9]Python
def merge_sort(items: list) -> list:
if len(items) <= 1: # a list of 0 or 1 elements is already sorted
return items
mid = len(items) // 2
left = merge_sort(items[:mid])
right = merge_sort(items[mid:])
return merge(left, right)
def merge(a: list, b: list) -> list:
merged = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
merged.append(a[i]); i += 1
else:
merged.append(b[j]); j += 1
return merged + a[i:] + b[j:]
print(merge_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9]
P75
Quick Sort
Pick a pivot, partition around it, recurse on each side.
Quick Sort
Pick a pivot, partition around it, recurse on each side.
Approach: pick the first element as a pivot, split the rest into "smaller than pivot" and "greater than or equal to pivot" buckets, recursively sort each bucket, then stitch them back together with the pivot in the middle.
JavaScript
// Pick a pivot, partition everything into "less than" and "greater than"
// buckets around it, then recursively sort each bucket.
function quickSort(arr) {
if (arr.length <= 1) return arr;
const [pivot, ...rest] = arr;
const left = rest.filter((n) => n < pivot);
const right = rest.filter((n) => n >= pivot);
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([5, 2, 9, 1, 5, 6])); // [1, 2, 5, 5, 6, 9]Python
def quick_sort(items: list) -> list:
if len(items) <= 1:
return items
pivot, *rest = items
left = [n for n in rest if n < pivot]
right = [n for n in rest if n >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9]
P76
Counting Sort
Sort non-negative integers by tallying, not comparing.
Counting Sort
Sort non-negative integers by tallying, not comparing.
Approach: only works for non-negative integers in a known range. Count how many times each value appears, then write each value back out that many times, in order — no comparisons between elements at all.
JavaScript
// Only works for non-negative integers in a known range -- count how many
// times each value appears, then read the counts back out in order.
function countingSort(arr) {
const max = Math.max(...arr);
const counts = new Array(max + 1).fill(0);
for (const n of arr) counts[n]++; // tally each value
const result = [];
for (let value = 0; value <= max; value++) {
for (let i = 0; i < counts[value]; i++) result.push(value); // write it out `count` times
}
return result;
}
console.log(countingSort([5, 2, 9, 1, 5, 6])); // [1, 2, 5, 5, 6, 9]Python
def counting_sort(items: list) -> list:
maximum = max(items)
counts = [0] * (maximum + 1)
for n in items:
counts[n] += 1 # tally each value
result = []
for value in range(maximum + 1):
result.extend([value] * counts[value]) # write it out `count` times
return result
print(counting_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9]
P77
Find the First Occurrence in a Sorted Array
[1,2,2,2,3,4] searching for 2 → index 1, the earliest one.
Find the First Occurrence in a Sorted Array
[1,2,2,2,3,4] searching for 2 → index 1, the earliest one.
Approach: a variant of Module 5's binary search. A plain binary search stops the moment it finds any match — to find the first one, record the match but keep narrowing into the left half, in case an earlier match exists.
JavaScript
// Standard binary search stops at ANY match. To find the FIRST one, keep
// searching the left half even after finding a match, in case an earlier one exists.
function firstOccurrence(sortedArr, target) {
let low = 0, high = sortedArr.length - 1, result = -1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (sortedArr[mid] === target) {
result = mid; // record it, but keep looking further left
high = mid - 1;
} else if (sortedArr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
console.log(firstOccurrence([1, 2, 2, 2, 3, 4], 2)); // 1Python
def first_occurrence(sorted_items: list, target) -> int:
low, high, result = 0, len(sorted_items) - 1, -1
while low <= high:
mid = (low + high) // 2
if sorted_items[mid] == target:
result = mid # record it, but keep looking further left
high = mid - 1
elif sorted_items[mid] < target:
low = mid + 1
else:
high = mid - 1
return result
print(first_occurrence([1, 2, 2, 2, 3, 4], 2)) # 1
P78
Find the Last Occurrence in a Sorted Array
[1,2,2,2,3,4] searching for 2 → index 3, the last one.
Find the Last Occurrence in a Sorted Array
[1,2,2,2,3,4] searching for 2 → index 3, the last one.
Approach: the mirror image of the previous problem — record a match and keep narrowing into the right half instead of the left.
JavaScript
// The mirror image of the previous problem: keep searching right after a match.
function lastOccurrence(sortedArr, target) {
let low = 0, high = sortedArr.length - 1, result = -1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (sortedArr[mid] === target) {
result = mid; // record it, but keep looking further right
low = mid + 1;
} else if (sortedArr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
console.log(lastOccurrence([1, 2, 2, 2, 3, 4], 2)); // 3Python
def last_occurrence(sorted_items: list, target) -> int:
low, high, result = 0, len(sorted_items) - 1, -1
while low <= high:
mid = (low + high) // 2
if sorted_items[mid] == target:
result = mid # record it, but keep looking further right
low = mid + 1
elif sorted_items[mid] < target:
low = mid + 1
else:
high = mid - 1
return result
print(last_occurrence([1, 2, 2, 2, 3, 4], 2)) # 3
P79
Search in a Rotated Sorted Array
[4,5,6,7,0,1,2] searching for 0 → index 4.
Search in a Rotated Sorted Array
[4,5,6,7,0,1,2] searching for 0 → index 4.
Approach: a rotated sorted array is still "half sorted" at every midpoint — at least one side is guaranteed to be in proper ascending order. Check which side that is, then decide whether the target could be hiding in it.
JavaScript
// A rotated sorted array is still "half sorted" at every step: at least one
// side of any midpoint is guaranteed to be in proper order. Check which side
// is sorted, then decide if the target could be in it.
function searchRotated(arr, target) {
let low = 0, high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) return mid;
if (arr[low] <= arr[mid]) { // left half is sorted
if (arr[low] <= target && target < arr[mid]) high = mid - 1;
else low = mid + 1;
} else { // right half is sorted
if (arr[mid] < target && target <= arr[high]) low = mid + 1;
else high = mid - 1;
}
}
return -1;
}
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4Python
def search_rotated(items: list, target) -> int:
low, high = 0, len(items) - 1
while low <= high:
mid = (low + high) // 2
if items[mid] == target:
return mid
if items[low] <= items[mid]: # left half is sorted
if items[low] <= target < items[mid]:
high = mid - 1
else:
low = mid + 1
else: # right half is sorted
if items[mid] < target <= items[high]:
low = mid + 1
else:
high = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4
P80
Find a Peak Element
[1,3,20,4,1,0] → index 2 (value 20), bigger than both neighbors.
Find a Peak Element
[1,3,20,4,1,0] → index 2 (value 20), bigger than both neighbors.
Approach: binary search still works even though the array isn't sorted, because at any midpoint you can tell which direction is "uphill" — walk toward the slope that's still climbing, and you'll land on a peak.
JavaScript
// A peak is bigger than both neighbors. Binary search works even though the
// array isn't sorted: walk toward whichever side is still climbing uphill.
function findPeak(arr) {
let low = 0, high = arr.length - 1;
while (low < high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] > arr[mid + 1]) {
high = mid; // downhill to the right -- the peak is at mid or to the left
} else {
low = mid + 1; // uphill to the right -- the peak is further right
}
}
return low; // low === high: the peak's index
}
console.log(findPeak([1, 3, 20, 4, 1, 0])); // 2 (value 20)Python
def find_peak(items: list) -> int:
low, high = 0, len(items) - 1
while low < high:
mid = (low + high) // 2
if items[mid] > items[mid + 1]:
high = mid # downhill to the right -- the peak is at mid or to the left
else:
low = mid + 1 # uphill to the right -- the peak is further right
return low # low == high: the peak's index
print(find_peak([1, 3, 20, 4, 1, 0])) # 2 (value 20)2. Key Takeaways
- Bubble, selection and insertion sort are all O(n²) — fine for small or nearly-sorted lists, but merge sort and quick sort's O(n log n) matters once the list gets large.
- Merge sort's "split, recurse, merge" and quick sort's "partition, recurse, combine" are the two dominant shapes behind almost every divide-and-conquer algorithm you'll meet later.
- Binary search isn't just for "find this exact value" — the same halving logic finds a boundary (first/last occurrence), survives a rotation, and even works on unsorted data if there's still a monotonic direction to follow (peak-finding).