ヒープソートとカウントソートの解説と比較

2024年9月5日

今日のトピックは、「ヒープソート」と「カウントソート」という2つの異なるソートアルゴリズムです。ヒープソートは比較ベースのソートであり、効率的なメモリ使用が特徴です。一方、カウントソートはキーの範囲が限られている場合に非常に効率的に動作します。

基本概念の説明

ヒープソート

ヒープソート: ヒープソートは、データ構造であるヒープを使って配列をソートするアルゴリズムです。最大ヒープ（または最小ヒープ）を利用して、要素を順に取り出し、ソート済みのリストを構築します。時間計算量は最悪の場合でも O(n \log n) であり、安定なソートではありませんが、追加メモリがほとんど必要ない点が特徴です。

カウントソート

カウントソート: カウントソートは、キー（要素）の範囲が限定されている場合に効率的なソートアルゴリズムです。要素の出現回数をカウントし、その情報を基に要素を並べ替えます。時間計算量は O(n + k) （ここで k は最大値）であり、キーの範囲が狭い場合に非常に効率的です。

各言語でのサンプルコード

Python:

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapsort(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

def countsort(arr):
    max_val = max(arr)
    m = max_val + 1
    count = [0] * m

    for a in arr:
        count[a] += 1
    i = 0
    for a in range(m):
        for c in range(count[a]):
            arr[i] = a
            i += 1

arr = [4, 10, 3, 5, 1]
heapsort(arr)
print("Heapsort:", arr)

arr = [4, 10, 3, 5, 1]
countsort(arr)
print("Countsort:", arr)

C#:

using System;

class SortAlgorithms
{
    public static void Heapify(int[] arr, int n, int i)
    {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < n && arr[l] > arr[largest])
            largest = l;
        if (r < n && arr[r] > arr[largest])
            largest = r;
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            Heapify(arr, n, largest);
        }
    }

    public static void HeapSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = n / 2 - 1; i >= 0; i--)
            Heapify(arr, n, i);
        for (int i = n - 1; i > 0; i--)
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            Heapify(arr, i, 0);
        }
    }

    public static void CountSort(int[] arr)
    {
        int max = arr[0];
        foreach (int num in arr)
            if (num > max)
                max = num;

        int[] count = new int[max + 1];
        foreach (int num in arr)
            count[num]++;

        int index = 0;
        for (int i = 0; i < count.Length; i++)
            while (count[i]-- > 0)
                arr[index++] = i;
    }

    static void Main()
    {
        int[] arr = {4, 10, 3, 5, 1};
        HeapSort(arr);
        Console.WriteLine("Heapsort: " + string.Join(",", arr));

        arr = new int[] {4, 10, 3, 5, 1};
        CountSort(arr);
        Console.WriteLine("Countsort: " + string.Join(",", arr));
    }
}

C++:

#include <iostream>
#include <vector>

using namespace std;

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapsort(vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

void countsort(vector<int>& arr) {
    int max_val = *max_element(arr.begin(), arr.end());
    vector<int> count(max_val + 1, 0);

    for (int num : arr)
        count[num]++;

    int index = 0;
    for (int i = 0; i <= max_val; i++)
        while (count[i]--)
            arr[index++] = i;
}

int main() {
    vector<int> arr = {4, 10, 3, 5, 1};
    heapsort(arr);
    cout << "Heapsort: ";
    for (int n : arr) cout << n << " ";
    cout << endl;

    arr = {4, 10, 3, 5, 1};
    countsort(arr);
    cout << "Countsort: ";
    for (int n : arr) cout << n << " ";
    cout << endl;

    return 0;
}

Java:

import java.util.Arrays;

public class SortAlgorithms {
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < n && arr[l] > arr[largest])
            largest = l;
        if (r < n && arr[r] > arr[largest])
            largest = r;
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }

    public static void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    public static void countSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[max + 1];

        for (int num : arr)
            count[num]++;

        int index = 0;
        for (int i = 0; i <= max; i++)
            while (count[i]-- > 0)
                arr[index++] = i;
    }

    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        heapSort(arr);
        System.out.println("Heapsort: " + Arrays.toString(arr));

        arr = new int[]{4, 10, 3, 5, 1};
        countSort(arr);
        System.out.println("Countsort: " + Arrays.toString(arr));
    }
}

JavaScript:

function heapify(arr, n, i) {
    let largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

function heapsort(arr) {
    let n = arr.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
}

function countsort(arr) {
    let max = Math.max(...arr);
    let count = new Array(max + 1).fill(0);

    for (let num of arr)
        count[num]++;

    let index = 0;
    for (let i = 0; i <= max; i++)
        while (count[i]-- > 0)
            arr[index++] = i;
}

let arr = [4, 10, 3, 5, 1];
heapsort(arr);
console.log("Heapsort:", arr);

arr = [4, 10, 3, 5, 1];
countsort(arr);
console.log("Countsort:", arr);

各言語の解説

Python: ヒープソートとカウントソートを簡潔に実装しており、特にカウントソートはPythonのリスト操作が強力で直感的です。

C#: C#では、ヒープソートの再帰的ヒープ化とカウントソートの簡単な実装を提供しています。配列の操作が非常に効率的です。

C++: C++のstd::vectorを使用して効率的にヒープソートとカウントソートを実装しています。標準ライブラリの関数も活用しています。

Java: Javaでは、配列の操作にArraysクラスのメソッドを使用し、ヒープソートとカウントソートを実装しています。

JavaScript: JavaScriptの配列操作を活用し、ヒープソートとカウントソートを実装しています。スプレッド構文やMathライブラリが役立っています。

まとめ

ヒープソートはメモリ効率が高く、比較ベースのソートアルゴリズムとして広く使われています。一方、カウントソートはキーの範囲が狭い場合に非常に効率的で、特に整数配列のソートに適しています。

次回は、ラジックスソートやその他のソートアルゴリズムについて学び、異なる状況で最適なソート手法を選択する方法を検討します。

よかったらシェアしてね！

URLをコピーしました！

URLをコピーしました！

コメント一覧（1件）

プログラミング学習ガイド | カテゴリ別目次 より:

2024年9月6日 9:04 PM

[…] 1-4-2. ヒープソートとカウントソート […]

返信