Sorting
9 problems from Rosalind — Algorithmic Heights. Press Run on any block to execute it in your browser.
INS — Insertion Sort
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
The swap count is the number of inversions, so the same loop answers INV as well. Sorts in place, which the index assignment added for these packs is what makes possible.
# Rosalind: INS — Insertion Sort
# https://rosalind.info/problems/ins/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: The number of swaps performed by insertion sort on A[1..n].
let a = [6, 10, 4, 5, 1, 2]
# Insertion sort walks each element back past everything larger than it, so the
# swap count is exactly the number of inversions in the array. The sort is done
# in place, which is what makes the count meaningful.
let xs = a
let swaps = 0
let i = 1
while i < len(xs) {
let k = i
while k > 0 and xs[k] < xs[k - 1] {
let held = xs[k]
xs[k] = xs[k - 1]
xs[k - 1] = held
swaps = swaps + 1
k = k - 1
}
i = i + 1
}
println("Result: " + str(swaps))
println("Expected: 12")
println("Sorted: " + str(xs))
fn test_ins_counts_swaps() {
assert swaps == 12, "INS: got " + str(swaps)
assert xs == [1, 2, 4, 5, 6, 10], "INS: the array was not sorted in place: " + str(xs)
}MER — Merge Two Sorted Arrays
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: MER — Merge Two Sorted Arrays
# https://rosalind.info/problems/mer/
#
# Given: A sorted array A[1..n] and a sorted array B[1..m].
# Return: A sorted array C[1..n+m] containing all elements of A and B.
let a = [2, 4, 10, 18]
let b = [-5, 11, 12]
# The merge step of merge sort. Sorting the concatenation would also work and
# would also be slower: taking the smaller head each time is linear because both
# inputs are already ordered.
let merged = []
let i = 0
let j = 0
while i < len(a) and j < len(b) {
if a[i] <= b[j] {
merged = push(merged, a[i])
i = i + 1
} else {
merged = push(merged, b[j])
j = j + 1
}
}
while i < len(a) {
merged = push(merged, a[i])
i = i + 1
}
while j < len(b) {
merged = push(merged, b[j])
j = j + 1
}
let result = merged |> map(|v| str(v)) |> join(" ")
println("Result: " + result)
println("Expected: -5 2 4 10 11 12 18")
fn test_mer_merges_in_order() {
assert result == "-5 2 4 10 11 12 18", "MER: got " + result
}MS — Merge Sort
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: MS — Merge Sort
# https://rosalind.info/problems/ms/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A sorted array A[1..n].
let a = [20, 19, 35, -18, 17, -20, 20, 1, 4, 4]
fn merge(left, right) {
let out = []
let i = 0
let j = 0
while i < len(left) and j < len(right) {
# `<=` rather than `<` keeps equal elements in their original order,
# which is what makes this sort stable. The array holds 4 twice and 20
# twice, so the distinction is live here.
if left[i] <= right[j] {
out = push(out, left[i])
i = i + 1
} else {
out = push(out, right[j])
j = j + 1
}
}
while i < len(left) {
out = push(out, left[i])
i = i + 1
}
while j < len(right) {
out = push(out, right[j])
j = j + 1
}
out
}
fn merge_sort(xs) {
if len(xs) <= 1 {
xs
} else {
let middle = int(len(xs) / 2)
merge(merge_sort(slice(xs, 0, middle)), merge_sort(slice(xs, middle, len(xs))))
}
}
let sorted = merge_sort(a)
let result = sorted |> map(|v| str(v)) |> join(" ")
println("Result: " + result)
println("Expected: -20 -18 1 4 4 17 19 20 20 35")
fn test_ms_sorts_the_array() {
assert result == "-20 -18 1 4 4 17 19 20 20 35", "MS: got " + result
}PAR — 2-Way Partition
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Any valid partition is accepted, so the three conditions are asserted rather than one arrangement.
# Rosalind: PAR — 2-Way Partition
# https://rosalind.info/problems/par/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A permutation B of A with an index q such that everything before q is
# <= A[1], B[q] = A[1], and everything after q is > A[1].
let a = [7, 2, 5, 6, 1, 3, 9, 4, 8]
# Lomuto's scheme: one pass, with a boundary that marks where the "not greater
# than the pivot" run ends. The pivot is parked at the front during the sweep
# and swapped into the boundary at the end, which is what puts it at q.
let xs = a
let pivot = xs[0]
let boundary = 1
let j = 1
while j < len(xs) {
if xs[j] <= pivot {
let held = xs[boundary]
xs[boundary] = xs[j]
xs[j] = held
boundary = boundary + 1
}
j = j + 1
}
let held = xs[0]
xs[0] = xs[boundary - 1]
xs[boundary - 1] = held
let q = boundary - 1
let result = xs |> map(|v| str(v)) |> join(" ")
# Every partition around this pivot is accepted, so the three conditions are
# checked rather than one particular arrangement. The sample output is
# 5 6 3 4 1 2 7 9 8; this sweep produces a different valid one.
let before_ok = range(0, q) |> filter(|i| xs[i] > pivot)
let after_ok = range(q + 1, len(xs)) |> filter(|i| xs[i] <= pivot)
println("Result: " + result)
println("Sample: 5 6 3 4 1 2 7 9 8")
println("Pivot " + str(pivot) + " sits at 1-based index " + str(q + 1))
fn test_par_partitions_around_the_pivot() {
assert xs[q] == pivot, "PAR: the pivot is not at q, got " + str(xs[q])
assert len(before_ok) == 0, "PAR: values greater than the pivot before q at " + str(before_ok)
assert len(after_ok) == 0, "PAR: values not greater than the pivot after q at " + str(after_ok)
assert sort(xs) == sort(a), "PAR: the result is not a permutation of the input: " + result
}HS — Heap Sort
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: HS — Heap Sort
# https://rosalind.info/problems/hs/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A sorted array A.
let a = [2, 6, 7, 1, 3, 5, 4, 8, 9]
fn sift_down(heap, start, size) {
let xs = heap
let root = start
let settled = false
while settled == false {
let largest = root
let left = 2 * root + 1
let right = 2 * root + 2
if left < size and xs[left] > xs[largest] then largest = left
if right < size and xs[right] > xs[largest] then largest = right
if largest == root {
settled = true
} else {
let held = xs[root]
xs[root] = xs[largest]
xs[largest] = held
root = largest
}
}
xs
}
# Build the max heap (as in HEA), then repeatedly move the largest element to
# the end and shrink the heap by one. The sorted tail grows from the right, so
# no second array is needed — this sorts in place.
let xs = a
let node = int(len(xs) / 2) - 1
while node >= 0 {
xs = sift_down(xs, node, len(xs))
node = node - 1
}
let size = len(xs)
while size > 1 {
let held = xs[0]
xs[0] = xs[size - 1]
xs[size - 1] = held
size = size - 1
xs = sift_down(xs, 0, size)
}
let result = xs |> map(|v| str(v)) |> join(" ")
println("Result: " + result)
println("Expected: 1 2 3 4 5 6 7 8 9")
fn test_hs_sorts_the_array() {
assert result == "1 2 3 4 5 6 7 8 9", "HS: got " + result
}INV — Counting Inversions
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Counted during the merge rather than pairwise, so this is n log n where INS's swap count is quadratic. The two problems ask for the same number.
# Rosalind: INV — Counting Inversions
# https://rosalind.info/problems/inv/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: The number of inversions in A.
let a = [-6, 1, 15, 8, 10]
# Counted during a merge sort rather than by comparing every pair. When the
# merge takes an element from the right half, every element still waiting in the
# left half is greater than it and forms an inversion with it, so the whole
# remaining left half can be counted at once. That is what makes this n log n
# where INS's swap count is quadratic — the two problems ask for the same number.
let inversions = 0
fn merge_count(left, right) {
let out = []
let i = 0
let j = 0
while i < len(left) and j < len(right) {
if left[i] <= right[j] {
out = push(out, left[i])
i = i + 1
} else {
out = push(out, right[j])
j = j + 1
inversions = inversions + (len(left) - i)
}
}
while i < len(left) {
out = push(out, left[i])
i = i + 1
}
while j < len(right) {
out = push(out, right[j])
j = j + 1
}
out
}
fn sort_and_count(xs) {
if len(xs) <= 1 {
xs
} else {
let middle = int(len(xs) / 2)
merge_count(sort_and_count(slice(xs, 0, middle)), sort_and_count(slice(xs, middle, len(xs))))
}
}
let sorted = sort_and_count(a)
println("Result: " + str(inversions))
println("Expected: 2")
println("Sorted: " + str(sorted))
fn test_inv_counts_inversions() {
assert inversions == 2, "INV: got " + str(inversions)
assert sorted == sort(a), "INV: the merge did not sort: " + str(sorted)
}PAR3 — 3-Way Partition
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Dutch national flag. Any valid arrangement is accepted, so the three regions are asserted rather than one output; this one happens to match the sample.
# Rosalind: PAR3 — 3-Way Partition
# https://rosalind.info/problems/par3/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A permutation B of A with indices q <= r such that B[i] < A[1] before
# q, B[i] = A[1] from q to r, and B[i] > A[1] after r.
let a = [4, 5, 6, 4, 1, 2, 5, 7, 4]
# Dijkstra's Dutch national flag: one pass, three regions. `low` ends the run
# below the pivot, `high` begins the run above it, and `scan` walks the unknown
# middle. Swapping down from `high` does not advance `scan`, because the value
# swapped in has not been looked at yet — the array holds 4 three times, so the
# equal region is what this problem is really testing.
let xs = a
let pivot = xs[0]
let low = 0
let cursor = 0
let high = len(xs) - 1
while cursor <= high {
if xs[cursor] < pivot {
let held = xs[low]
xs[low] = xs[cursor]
xs[cursor] = held
low = low + 1
cursor = cursor + 1
} else {
if xs[cursor] > pivot {
let held = xs[high]
xs[high] = xs[cursor]
xs[cursor] = held
high = high - 1
} else {
cursor = cursor + 1
}
}
}
let result = xs |> map(|v| str(v)) |> join(" ")
# Any valid arrangement is accepted, so the three regions are checked rather
# than one particular output. The sample shows 2 1 4 4 4 5 7 6 5.
let below = range(0, low) |> filter(|i| xs[i] >= pivot)
let equal = range(low, high + 1) |> filter(|i| xs[i] != pivot)
let above = range(high + 1, len(xs)) |> filter(|i| xs[i] <= pivot)
println("Result: " + result)
println("Sample: 2 1 4 4 4 5 7 6 5")
println("Regions: below " + str(low) + ", equal " + str(high + 1 - low) + ", above " + str(len(xs) - high - 1))
fn test_par3_three_regions() {
assert len(below) == 0, "PAR3: not-smaller values before q at " + str(below)
assert len(equal) == 0, "PAR3: values other than the pivot between q and r at " + str(equal)
assert len(above) == 0, "PAR3: not-greater values after r at " + str(above)
assert sort(xs) == sort(a), "PAR3: the result is not a permutation of the input: " + result
}PS — Partial Sort
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: PS — Partial Sort
# https://rosalind.info/problems/ps/
#
# Given: A positive integer n, an array A[1..n] of integers, and a positive
# integer k.
# Return: The k smallest elements of a sorted array A.
let a = [4, -6, 7, 8, -9, 100, 12, 13, 56, 17]
let k = 3
# Only the first k elements are wanted, so a heap of size k is the usual answer:
# it keeps the work at n log k rather than n log n. With k = 3 out of 10 the
# distinction is academic, so this takes the direct route and sorts. The shape
# of the answer is the same; PS and MED together are the pair worth comparing,
# since MED shows the selection that avoids the full sort.
let smallest = slice(sort(a), 0, k)
let result = smallest |> map(|v| str(v)) |> join(" ")
println("Result: " + result)
println("Expected: -9 -6 4")
fn test_ps_k_smallest() {
assert result == "-9 -6 4", "PS: got " + result
assert len(smallest) == k, "PS: expected " + str(k) + " values, got " + str(len(smallest))
}QS — Quick Sort
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: QS — Quick Sort
# https://rosalind.info/problems/qs/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A sorted array A[1..n].
let a = [5, -2, 4, 7, 8, -10, 11]
# Partition around a pivot, then sort each side. Splitting into three parts
# rather than two keeps duplicates out of the recursion: everything equal to the
# pivot is already in its final place, so neither side has to carry it. That is
# the same split MED uses to select without sorting.
fn quicksort(xs) {
if len(xs) <= 1 {
xs
} else {
let pivot = xs[int(len(xs) / 2)]
let below = xs |> filter(|v| v < pivot)
let equal = xs |> filter(|v| v == pivot)
let above = xs |> filter(|v| v > pivot)
concat(concat(quicksort(below), equal), quicksort(above))
}
}
let sorted = quicksort(a)
let result = sorted |> map(|v| str(v)) |> join(" ")
println("Result: " + result)
println("Expected: -10 -2 4 5 7 8 11")
fn test_qs_sorts_the_array() {
assert result == "-10 -2 4 5 7 8 11", "QS: got " + result
assert sorted == sort(a), "QS: disagrees with the builtin sort: " + result
}