今日のトピックは「バブルソート、選択ソート、挿入ソートの違いと実装方法」です。これらは基本的なソートアルゴリズムで、データを並べ替える際に使用されます。
各ソートアルゴリズムの特性を理解し、適切に使い分けることで、効率的にデータを処理することができます。
目次
基本概念の説明
バブルソート(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 | ループで隣り合う要素を比較・交換 | ループで最小値を選択・交換 | ループで要素を適切な位置に挿入 |
まとめ
今日は、バブルソート、選択ソート、挿入ソートの違いとそれぞれの実装方法について学びました。これらのアルゴリズムは、基本的なソート方法であり、データの並び替えに広く利用されています。
次回は、これらのソートアルゴリズムの応用や、さらに効率的なソート方法について学びましょう。
コメント
コメント一覧 (1件)
[…] 3-4-2. バブルソート、選択ソート、挿入ソート […]