今日のトピックは、アルゴリズムの中でも代表的なソート手法である「クイックソート」と「マージソート」です。これらのソートアルゴリズムは、どちらも分割統治法に基づいていますが、それぞれのアルゴリズムには特徴的な違いがあり、用途に応じた使い分けが重要です。
目次
基本概念の説明
クイックソート
クイックソート: クイックソートは、ピボットと呼ばれる基準値を選び、配列をそのピボットを基準に2つの部分に分けるソート手法です。その後、それぞれの部分を再帰的にソートし、最終的に整列された配列を得ます。クイックソートは平均時間計算量が O(n \log n) であり、メモリ効率が良い点が特徴です。
マージソート
マージソート: マージソートは、配列を半分に分割し、それぞれを再帰的にソートした後、2つの部分をマージ（併合）するソート手法です。安定なソートであり、最悪でも O(n \log n) の計算量で動作しますが、追加のメモリが必要になります。
各言語でのサンプルコード
Python:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
def mergesort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = mergesort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result.extend(left or right)
return result
arr = [3,6,8,10,1,2,1]
print("Quicksort:", quicksort(arr))
print("Mergesort:", mergesort(arr))C#:
using System;
using System.Collections.Generic;
class SortAlgorithms
{
static void QuickSort(int[] arr, int left, int right)
{
int i = left, j = right;
int pivot = arr[(left + right) / 2];
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
if (left < j)
QuickSort(arr, left, j);
if (i < right)
QuickSort(arr, i, right);
}
static int[] MergeSort(int[] arr)
{
if (arr.Length <= 1)
return arr;
int mid = arr.Length / 2;
int[] left = new int[mid];
int[] right = new int[arr.Length - mid];
Array.Copy(arr, 0, left, 0, mid);
Array.Copy(arr, mid, right, 0, arr.Length - mid);
left = MergeSort(left);
right = MergeSort(right);
return Merge(left, right);
}
static int[] Merge(int[] left, int[] right)
{
List result = new List();
int i = 0, j = 0;
while (i < left.Length && j < right.Length)
{
if (left[i] <= right[j])
result.Add(left[i++]);
else
result.Add(right[j++]);
}
result.AddRange(i < left.Length ? left[i..] : right[j..]);
return result.ToArray();
}
static void Main()
{
int[] arr = {3,6,8,10,1,2,1};
QuickSort(arr, 0, arr.Length - 1);
Console.WriteLine("Quicksort: " + string.Join(",", arr));
arr = new int[] {3,6,8,10,1,2,1};
int[] sortedArr = MergeSort(arr);
Console.WriteLine("Mergesort: " + string.Join(",", sortedArr));
}
}C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void quicksort(vector<int>& arr, int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
if (left < j)
quicksort(arr, left, j);
if (i < right)
quicksort(arr, i, right);
}
vector<int> merge(vector<int> left, vector<int> right) {
vector<int> result;
while (!left.empty() && !right.empty()) {
if (left.front() <= right.front()) {
result.push_back(left.front());
left.erase(left.begin());
} else {
result.push_back(right.front());
right.erase(right.begin());
}
}
result.insert(result.end(), left.begin(), left.end());
result.insert(result.end(), right.begin(), right.end());
return result;
}
vector<int> mergesort(vector<int>& arr) {
if (arr.size() <= 1)
return arr;
int mid = arr.size() / 2;
vector<int> left(arr.begin(), arr.begin() + mid);
vector<int> right(arr.begin() + mid, arr.end());
left = mergesort(left);
right = mergesort(right);
return merge(left, right);
}
int main() {
vector<int> arr = {3,6,8,10,1,2,1};
quicksort(arr, 0, arr.size() - 1);
cout << "Quicksort: ";
for (int n : arr)
cout << n << " ";
cout << endl;
arr = {3,6,8,10,1,2,1};
vector<int> sortedArr = mergesort(arr);
cout << "Mergesort: ";
for (int n : sortedArr)
cout << n << " ";
cout << endl;
return 0;
}Java:
import java.util.Arrays;
public class SortAlgorithms {
public static void quicksort(int[] arr, int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left < j)
quicksort(arr, left, j);
if (i < right)
quicksort(arr, i, right);
}
public static int[] mergesort(int[] arr) {
if (arr.length <= 1)
return arr;
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
return merge(mergesort(left), mergesort(right));
}
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result[k++] = left[i++];
} else {
result[k++] = right[j++];
}
}
while (i < left.length) {
result[k++] = left[i++];
}
while (j < right.length) {
result[k++] = right[j++];
}
return result;
}
public static void main(String[] args) {
int[] arr = {3,6,8,10,1,2,1};
quicksort(arr, 0, arr.length - 1);
System.out.println("Quicksort: " + Arrays.toString(arr));
arr = new int[]{3,6,8,10,1,2,1};
int[] sortedArr = mergesort(arr);
System.out.println("Mergesort: " + Arrays.toString(sortedArr));
}
}JavaScript:
function quicksort(arr) {
if (arr.length <= 1) return arr;
let pivot = arr[Math.floor(arr.length / 2)];
let left = arr.filter(x => x < pivot);
let right = arr.filter(x => x > pivot);
let middle = arr.filter(x => x === pivot);
return [...quicksort(left), ...middle, ...quicksort(right)];
}
function mergesort(arr) {
if (arr.length <= 1) return arr;
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(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] < right[0]) result.push(left.shift());
else result.push(right.shift());
}
return result.concat(left, right);
}
let arr = [3,6,8,10,1,2,1];
console.log("Quicksort:", quicksort(arr));
console.log("Mergesort:", mergesort(arr));各言語の解説
Python: クイックソートとマージソートの両方を簡潔に実装しています。Pythonのリスト操作が強力で、直感的なコードを書きやすいです。
C#: C#では、クイックソートを再帰的に行い、マージソートでは追加の配列を用いてマージ操作を行っています。
C++: C++のstd::vectorを使用して、効率的に配列を操作しています。クイックソートのswap関数は標準ライブラリのものを使用しています。
Java: Javaでは配列のコピーにArrays.copyOfRangeを使用し、クイックソートとマージソートを実装しています。
JavaScript: JavaScriptの配列操作を活用し、クイックソートとマージソートをそれぞれ実装しています。スプレッド構文を使った結合が特徴的です。
まとめ
クイックソートは、メモリ効率が良く、平均的には非常に高速なソートアルゴリズムです。一方、マージソートは安定なソートであり、最悪の場合でも安定した時間計算量を持ちます。
次回は、ヒープソートや他のソートアルゴリズムを学び、どのような状況でどのソートを選ぶべきかを検討します。
コメント