バブルソート、選択ソート、挿入ソートの違いと実装方法

bubble-selection-insertion-sort

今日のトピックは「バブルソート、選択ソート、挿入ソートの違いと実装方法」です。これらは基本的なソートアルゴリズムで、データを並べ替える際に使用されます。

各ソートアルゴリズムの特性を理解し、適切に使い分けることで、効率的にデータを処理することができます。

目次

基本概念の説明

バブルソート(Bubble Sort)

バブルソート(Bubble Sort)は、隣り合う要素を比較して交換しながらリストを反復するソートアルゴリズムです。最も大きい要素が順番にリストの最後に「浮かび上がる」ように見えることから、この名前が付けられています。

選択ソート(Selection Sort)

選択ソート(Selection Sort)は、未ソート部分から最小または最大の要素を選び、それをリストの先頭に移動させるソートアルゴリズムです。この操作をリスト全体で繰り返します。

挿入ソート(Insertion Sort)

挿入ソート(Insertion Sort)は、リストの各要素を順に取り出し、適切な位置に挿入することでリストをソートするアルゴリズムです。すでにソートされた部分列を利用しながらソートが進行するため、効率的な処理が可能です。

各言語でのバブルソート、選択ソート、挿入ソートの実装例

Python:

# バブルソート
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 選択ソート
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 挿入ソート
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

C#:

using System;

class Program
{
    static void BubbleSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    static void SelectionSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++)
        {
            int minIdx = i;
            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[minIdx])
                    minIdx = j;
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    static void InsertionSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 1; i < n; i++)
        {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    static void Main()
    {
        int[] numbers = { 64, 25, 12, 22, 11 };

        BubbleSort(numbers);
        Console.WriteLine("バブルソート: " + string.Join(", ", numbers));

        numbers = new int[] { 64, 25, 12, 22, 11 };
        SelectionSort(numbers);
        Console.WriteLine("選択ソート: " + string.Join(", ", numbers));

        numbers = new int[] { 64, 25, 12, 22, 11 };
        InsertionSort(numbers);
        Console.WriteLine("挿入ソート: " + string.Join(", ", numbers));
    }
}

C++:

#include <iostream>
#include <vector>

void bubble_sort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

void selection_sort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        std::swap(arr[i], arr[min_idx]);
    }
}

void insertion_sort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    std::vector<int> numbers = {64, 25, 12, 22, 11};

    bubble_sort(numbers);
    std::cout << "バブルソート: ";
    for (int num : numbers) std::cout << num << " ";
    std::cout << std::endl;

    numbers = {64, 25, 12, 22, 11};
    selection_sort(numbers);
    std::cout << "選択ソート: ";
    for (int num : numbers) std::cout << num << " ";
    std::cout << std::endl;

    numbers = {64, 25, 12, 22, 11};
    insertion_sort(numbers);
    std::cout << "挿入ソート: ";
    for (int num : numbers) std::cout << num << " ";
    std::cout << std::endl;

    return 0;
}

Java:

public class Main {

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {64, 25, 12, 22, 11};

        bubbleSort(numbers);
        System.out.println("バブルソート: " + java.util.Arrays.toString(numbers));

        numbers = new int[]{64, 25, 12, 22, 11};
        selectionSort(numbers);
        System.out.println("選択ソート: " + java.util.Arrays.toString(numbers));

        numbers = new int[]{64, 25, 12, 22, 11};
        insertionSort(numbers);
        System.out.println("挿入ソート: " + java.util.Arrays.toString(numbers));
    }
}

JavaScript:

// バブルソート
function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n-1; i++) {
        for (let j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr;
}

// 選択ソート
function selectionSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n-1; i++) {
        let minIdx = i;
        for (let j = i+1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
    return arr;
}

// 挿入ソート
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

// 実行例
let numbers = [64, 25, 12, 22, 11];

console.log("バブルソート:", bubbleSort([...numbers]));
console.log("選択ソート:", selectionSort([...numbers]));
console.log("挿入ソート:", insertionSort([...numbers]));

各言語の解説

言語バブルソートの実装方法選択ソートの実装方法挿入ソートの実装方法
Pythonループで隣り合う要素を比較・交換ループで最小値を選択・交換ループで要素を適切な位置に挿入
C#ループで隣り合う要素を比較・交換ループで最小値を選択・交換ループで要素を適切な位置に挿入
C++ループで隣り合う要素を比較・交換ループで最小値を選択・交換ループで要素を適切な位置に挿入
Javaループで隣り合う要素を比較・交換ループで最小値を選択・交換ループで要素を適切な位置に挿入
JavaScriptループで隣り合う要素を比較・交換ループで最小値を選択・交換ループで要素を適切な位置に挿入

まとめ

今日は、バブルソート、選択ソート、挿入ソートの違いとそれぞれの実装方法について学びました。これらのアルゴリズムは、基本的なソート方法であり、データの並び替えに広く利用されています。

次回は、これらのソートアルゴリズムの応用や、さらに効率的なソート方法について学びましょう。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメント一覧 (1件)

コメントする

目次