【C言語】ポインタを用いてマージソートを実装する方法を解説

2023-09-102024-06-03

目次から探す

ポインタを用いたマージソートの実装

マージソートは、効率的なソートアルゴリズムの一つです。

この記事では、C言語でポインタを用いてマージソートを実装する方法について解説します。

ポインタの利用方法

ポインタは、変数やデータのメモリ上のアドレスを格納するための変数です。

マージソートでは、配列をポインタとして扱い、そのアドレスを操作することでソートを行います。

ポインタを使うことで、メモリの効率的な利用やデータの操作が可能になります。

ポインタを用いた配列の分割

マージソートでは、配列を分割してソートを行います。

ポインタを使うことで、配列を効率的に分割することができます。

具体的な手順としては、配列を半分に分割し、それぞれの部分配列を再帰的に分割していきます。

この際、ポインタを使って配列の範囲を指定し、分割を行います。

ポインタを用いた配列の統合

分割した部分配列をマージすることで、ソートされた配列を得ることができます。

ポインタを使って、統合する際の配列の範囲を指定し、統合を行います。

具体的な手順としては、2つの部分配列の先頭要素を比較し、小さい方を新しい配列に格納します。

その後、比較した要素のポインタを進め、再度比較を行います。

この操作を繰り返し、全ての要素を統合します。

サンプルコード

以下に、ポインタを用いたマージソートのサンプルコードを示します。

このサンプルコードでは、整数の配列をソートします。

配列をポインタとして扱い、ポインタの操作を行っています。

#include <stdio.h>
void merge(int* arr, int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(int* arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("ソート前の配列: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    mergeSort(arr, 0, n - 1);
    printf("\nソート後の配列: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}