ソート ガイド · 3/6
この章は現在、英語でのみ提供しています。
Merge sort and quicksort in Python, explained line by line, then the same merge sort in C++, Java and TypeScript.
def merge_sort(items):
if len(items) <= 1:
return items[:]
mid = len(items) // 2
left = merge_sort(items[:mid])
right = merge_sort(items[mid:])
return merge(left, right)
def merge(left, right):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
print(merge_sort([38, 27, 43, 3, 9, 82, 10])) # [3, 9, 10, 27, 38, 43, 82]len(items) <= 1: the base case. items[:] returns a copy, so the input is never modified.mid = len(items) // 2: split in the middle and sort each half recursively.merge loop appends the smaller of the two front elements.left[i] <= right[j]: on ties the left element goes first, which makes the sort stable. Using < would break stability.extend: when one side runs out, the sorted rest of the other is appended.Every slice allocates a new list; faster versions reuse one buffer and index ranges, as in C++ and Java below.
import random
def quicksort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
while lo < hi:
lt, gt = partition3(a, lo, hi)
if lt - lo < hi - gt: # recurse on the smaller side only
quicksort(a, lo, lt - 1)
lo = gt + 1
else:
quicksort(a, gt + 1, hi)
hi = lt - 1
def partition3(a, lo, hi):
pivot = a[random.randint(lo, hi)]
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt -= 1
else:
i += 1
return lt, gt
data = [5, 2, 8, 2, 9, 1, 5, 5]
quicksort(data)
print(data) # [1, 2, 2, 5, 5, 5, 8, 9]random.randint(lo, hi): a random pivot makes the O(n²) case unlikely on any input, including sorted data.partition3: a three-way partition (the Dutch national flag problem). Afterwards a[lo:lt] is smaller than the pivot, a[lt:gt+1] equals it and a[gt+1:hi+1] is larger. Equal keys are never revisited, so duplicates stay fast.a[i] > pivot branch i does not advance, because the value swapped in from a[gt] has not been examined yet.while lo < hi plus recursing on the smaller side caps recursion depth at O(log n), well below Python's default limit of 1000.#include <cstddef>
#include <iostream>
#include <vector>
template <typename T>
void merge_sort(std::vector<T>& a, std::vector<T>& buf, std::size_t lo, std::size_t hi) {
if (hi - lo <= 1) return; // half-open range [lo, hi)
std::size_t mid = lo + (hi - lo) / 2;
merge_sort(a, buf, lo, mid);
merge_sort(a, buf, mid, hi);
std::size_t i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
if (a[j] < a[i]) buf[k++] = a[j++]; // right only if strictly smaller: stable
else buf[k++] = a[i++];
}
while (i < mid) buf[k++] = a[i++];
while (j < hi) buf[k++] = a[j++];
for (std::size_t t = lo; t < hi; ++t) a[t] = buf[t];
}
template <typename T>
void merge_sort(std::vector<T>& a) {
std::vector<T> buf(a.size());
merge_sort(a, buf, 0, a.size());
}
int main() {
std::vector<int> v{38, 27, 43, 3, 9, 82, 10};
merge_sort(v);
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}One buffer, half-open ranges, and only operator<. In production code, std::stable_sort does this job.
import java.util.Arrays;
public class MergeSort {
public static void sort(int[] a) {
int[] buf = new int[a.length];
sort(a, buf, 0, a.length);
}
private static void sort(int[] a, int[] buf, int lo, int hi) {
if (hi - lo <= 1) return;
int mid = lo + (hi - lo) / 2; // no (lo + hi) overflow
sort(a, buf, lo, mid);
sort(a, buf, mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
buf[k++] = (a[j] < a[i]) ? a[j++] : a[i++];
}
while (i < mid) buf[k++] = a[i++];
while (j < hi) buf[k++] = a[j++];
System.arraycopy(buf, lo, a, lo, hi - lo);
}
public static void main(String[] args) {
int[] v = {38, 27, 43, 3, 9, 82, 10};
sort(v);
System.out.println(Arrays.toString(v));
}
}System.arraycopy copies the merged range back. For objects, take a Comparator<? super T> and test c.compare(a[j], a[i]) < 0.
function mergeSort<T>(items: readonly T[], compare: (a: T, b: T) => number): T[] {
if (items.length <= 1) return items.slice();
const mid = Math.floor(items.length / 2);
const left = mergeSort(items.slice(0, mid), compare);
const right = mergeSort(items.slice(mid), compare);
const merged: T[] = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (compare(right[j], left[i]) < 0) merged.push(right[j++]);
else merged.push(left[i++]);
}
while (i < left.length) merged.push(left[i++]);
while (j < right.length) merged.push(right[j++]);
return merged;
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10], (a, b) => a - b));The comparator follows the Array.prototype.sort contract (negative means a first), and T makes it generic.
コメント 0件
ログイン · ログインするとコメントできます。