MENU
  1. ホーム
  2. C++
  3. C++クラスで実装するソートアルゴリズムと応用例：完全ガイド

C++クラスで実装するソートアルゴリズムと応用例：完全ガイド

C++

C++のクラスを使ってソートアルゴリズムを実装する方法を詳しく解説します。本記事では、基本的なアルゴリズムの理解から具体的な実装方法、さらに実用的な応用例までを網羅し、読者が実際のプロジェクトで応用できるスキルを身に付けることを目指します。

目次

ソートアルゴリズムの基本概念

ソートアルゴリズムは、データを特定の順序に並べ替える手法であり、コンピュータサイエンスの基本的な課題の一つです。ソートには様々なアルゴリズムが存在し、それぞれに適した状況があります。C++のクラスを使用することで、ソートアルゴリズムをより効率的かつ直感的に実装することができます。

ソートアルゴリズムの種類

ソートアルゴリズムには、比較ベースのものと非比較ベースのものがあります。前者にはバブルソート、クイックソート、マージソートなどがあり、後者には基数ソートやバケットソートなどがあります。

クラスを使う意義

C++のクラスを用いることで、データ構造とその操作を一元化し、コードの再利用性と可読性を向上させることができます。特に、ソートアルゴリズムの実装においては、クラスを活用することで、複雑なデータ操作を簡潔に表現できます。

バブルソートの実装例

バブルソートは最も基本的なソートアルゴリズムの一つであり、隣接する要素を比較して必要に応じて入れ替えることでデータを並べ替えます。以下に、C++クラスを用いたバブルソートの実装例を示します。

バブルソートのアルゴリズム

バブルソートの基本的な動作は次の通りです:

  1. リストの先頭から末尾までの要素を順に比較します。
  2. 隣接する要素が逆順であれば入れ替えます。
  3. リスト全体がソートされるまでこの操作を繰り返します。

バブルソートの実装

以下は、C++のクラスを使ったバブルソートの実装例です。

#include <iostream>
#include <vector>

class BubbleSort {
public:
    void 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 printArray(const std::vector<int>& arr) {
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};
    BubbleSort bs;
    std::cout << "Unsorted array: ";
    bs.printArray(data);

    bs.sort(data);
    std::cout << "Sorted array: ";
    bs.printArray(data);

    return 0;
}

実装の解説

  • BubbleSortクラスには、バブルソートを実行するsortメソッドと、配列を出力するprintArrayメソッドがあります。
  • sortメソッドでは、二重ループを用いて隣接要素を比較し、必要に応じて入れ替えます。
  • printArrayメソッドは、配列の内容をコンソールに出力します。

この例では、ソート前とソート後の配列をコンソールに出力することで、バブルソートが正しく機能していることを確認できます。

クイックソートの実装例

クイックソートは、分割統治法に基づく効率的なソートアルゴリズムであり、大規模なデータセットのソートに適しています。以下に、C++クラスを用いたクイックソートの実装例を示します。

クイックソートのアルゴリズム

クイックソートの基本的な動作は次の通りです:

  1. 配列の要素から基準となるピボットを選びます。
  2. ピボットを基準にして配列を二つの部分に分けます。左側にはピボットより小さい要素、右側にはピボットより大きい要素が配置されます。
  3. 分割された部分に対して再帰的にクイックソートを適用します。

クイックソートの実装

以下は、C++のクラスを使ったクイックソートの実装例です。

#include <iostream>
#include <vector>

class QuickSort {
public:
    void sort(std::vector<int>& arr) {
        quicksort(arr, 0, arr.size() - 1);
    }

    void printArray(const std::vector<int>& arr) {
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

private:
    void quicksort(std::vector<int>& arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quicksort(arr, low, pi - 1);
            quicksort(arr, pi + 1, high);
        }
    }

    int partition(std::vector<int>& arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        return i + 1;
    }
};

int main() {
    std::vector<int> data = {10, 7, 8, 9, 1, 5};
    QuickSort qs;
    std::cout << "Unsorted array: ";
    qs.printArray(data);

    qs.sort(data);
    std::cout << "Sorted array: ";
    qs.printArray(data);

    return 0;
}

実装の解説

  • QuickSortクラスには、クイックソートを実行するsortメソッドと、配列を出力するprintArrayメソッドがあります。
  • quicksortメソッドは、配列を再帰的に分割してソートを行います。
  • partitionメソッドは、ピボットを基準に配列を二つに分割し、分割点のインデックスを返します。
  • sortメソッドが呼び出されると、quicksortメソッドが配列全体に対してクイックソートを適用します。

この例では、ソート前とソート後の配列をコンソールに出力することで、クイックソートが正しく機能していることを確認できます。

マージソートの実装例

マージソートは、分割統治法に基づくソートアルゴリズムであり、安定性と効率性が特徴です。以下に、C++クラスを用いたマージソートの実装例を示します。

マージソートのアルゴリズム

マージソートの基本的な動作は次の通りです:

  1. 配列を半分に分割します。
  2. 分割された各部分に対して再帰的にマージソートを適用します。
  3. 分割された部分をマージして、全体をソートします。

マージソートの実装

以下は、C++のクラスを使ったマージソートの実装例です。

#include <iostream>
#include <vector>

class MergeSort {
public:
    void sort(std::vector<int>& arr) {
        mergeSort(arr, 0, arr.size() - 1);
    }

    void printArray(const std::vector<int>& arr) {
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

private:
    void mergeSort(std::vector<int>& arr, int left, int right) {
        if (left < right) {
            int middle = left + (right - left) / 2;
            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);
            merge(arr, left, middle, right);
        }
    }

    void merge(std::vector<int>& arr, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        std::vector<int> leftArray(n1);
        std::vector<int> rightArray(n2);

        for (int i = 0; i < n1; ++i) {
            leftArray[i] = arr[left + i];
        }
        for (int i = 0; i < n2; ++i) {
            rightArray[i] = arr[middle + 1 + i];
        }

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }
};

int main() {
    std::vector<int> data = {12, 11, 13, 5, 6, 7};
    MergeSort ms;
    std::cout << "Unsorted array: ";
    ms.printArray(data);

    ms.sort(data);
    std::cout << "Sorted array: ";
    ms.printArray(data);

    return 0;
}

実装の解説

  • MergeSortクラスには、マージソートを実行するsortメソッドと、配列を出力するprintArrayメソッドがあります。
  • mergeSortメソッドは、配列を再帰的に分割してソートを行います。
  • mergeメソッドは、二つの分割された部分をマージして一つのソートされた配列にします。
  • sortメソッドが呼び出されると、mergeSortメソッドが配列全体に対してマージソートを適用します。

この例では、ソート前とソート後の配列をコンソールに出力することで、マージソートが正しく機能していることを確認できます。

ソートアルゴリズムのパフォーマンス比較

ソートアルゴリズムは、その効率性や適用範囲が異なるため、目的やデータの種類によって使い分ける必要があります。ここでは、バブルソート、クイックソート、マージソートのパフォーマンスを比較し、適切な選択をするための指針を示します。

計算量の比較

各ソートアルゴリズムの計算量を比較します。計算量は、アルゴリズムの効率性を示す指標であり、一般的には以下のようになります。

  • バブルソート: O(n^2)
  • クイックソート: 平均 O(n log n)、最悪 O(n^2)
  • マージソート: O(n log n)

パフォーマンステスト

以下のコードは、各アルゴリズムの実行時間を比較するためのサンプルです。

#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include "BubbleSort.h" // 前述のバブルソートクラス
#include "QuickSort.h"  // 前述のクイックソートクラス
#include "MergeSort.h"  // 前述のマージソートクラス

void measurePerformance() {
    const int SIZE = 10000;
    std::vector<int> data(SIZE);
    std::generate(data.begin(), data.end(), rand);

    BubbleSort bs;
    QuickSort qs;
    MergeSort ms;

    auto dataCopy = data;

    // Bubble Sort
    dataCopy = data;
    auto start = std::chrono::high_resolution_clock::now();
    bs.sort(dataCopy);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    std::cout << "Bubble Sort Time: " << elapsed.count() << " seconds" << std::endl;

    // Quick Sort
    dataCopy = data;
    start = std::chrono::high_resolution_clock::now();
    qs.sort(dataCopy);
    end = std::chrono::high_resolution_clock::now();
    elapsed = end - start;
    std::cout << "Quick Sort Time: " << elapsed.count() << " seconds" << std::endl;

    // Merge Sort
    dataCopy = data;
    start = std::chrono::high_resolution_clock::now();
    ms.sort(dataCopy);
    end = std::chrono::high_resolution_clock::now();
    elapsed = end - start;
    std::cout << "Merge Sort Time: " << elapsed.count() << " seconds" << std::endl;
}

int main() {
    measurePerformance();
    return 0;
}

実行結果の分析

実行結果から以下のような結論が導けます。

  • バブルソートはシンプルですが、計算量がO(n^2)のため、大規模なデータセットには適していません。
  • クイックソートは平均計算量がO(n log n)であり、実際のデータセットに対して高速に動作しますが、最悪ケースではO(n^2)になる可能性があります。
  • マージソートは常にO(n log n)の計算量を持ち、安定した性能を発揮しますが、追加のメモリが必要です。

アルゴリズムの選択基準

  • データセットが小規模な場合や、シンプルな実装が求められる場合はバブルソート。
  • 平均的な性能が重視され、最悪ケースの発生が少ないと予想される場合はクイックソート。
  • 安定性が必要で、大規模なデータセットに対しても一貫した性能を発揮する必要がある場合はマージソート。

以上の比較と分析により、用途や状況に応じた最適なソートアルゴリズムを選択するための指針が得られます。

クラスを使った応用例

クラスを活用することで、ソートアルゴリズムをより実用的に適用することができます。ここでは、現実のアプリケーションでの応用例として、学生の成績管理システムを紹介します。このシステムでは、学生の成績をソートするためにソートアルゴリズムを使用します。

学生クラスの定義

まず、学生の情報を管理するためのクラスを定義します。このクラスには、学生の名前、学籍番号、成績などの情報が含まれます。

#include <iostream>
#include <vector>
#include <string>

class Student {
public:
    std::string name;
    int id;
    double grade;

    Student(std::string name, int id, double grade)
        : name(name), id(id), grade(grade) {}
};

学生リストのソート

次に、学生の成績をソートするためにクイックソートアルゴリズムを使用します。ここでは、クイックソートクラスを改良し、学生の成績に基づいてソートする方法を示します。

class StudentSort {
public:
    void sort(std::vector<Student>& students) {
        quicksort(students, 0, students.size() - 1);
    }

private:
    void quicksort(std::vector<Student>& students, int low, int high) {
        if (low < high) {
            int pi = partition(students, low, high);
            quicksort(students, low, pi - 1);
            quicksort(students, pi + 1, high);
        }
    }

    int partition(std::vector<Student>& students, int low, int high) {
        double pivot = students[high].grade;
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (students[j].grade > pivot) {
                i++;
                std::swap(students[i], students[j]);
            }
        }
        std::swap(students[i + 1], students[high]);
        return i + 1;
    }
};

実装の解説

  • Studentクラスは、学生の情報を管理します。
  • StudentSortクラスは、学生の成績を基準にクイックソートアルゴリズムを使用してソートします。
  • partitionメソッドは、ピボットを基準に学生の成績を分割します。

使用例

以下のコードは、学生のリストを作成し、成績に基づいてソートする例です。

int main() {
    std::vector<Student> students = {
        {"Alice", 1001, 85.5},
        {"Bob", 1002, 92.3},
        {"Charlie", 1003, 78.9},
        {"David", 1004, 88.4},
        {"Eve", 1005, 91.2}
    };

    StudentSort sorter;
    sorter.sort(students);

    std::cout << "Students sorted by grade (descending order):" << std::endl;
    for (const auto& student : students) {
        std::cout << student.name << " (" << student.id << "): " << student.grade << std::endl;
    }

    return 0;
}

実装の解説

  • main関数で、学生のリストを作成し、StudentSortクラスのsortメソッドを使用して成績に基づいてソートします。
  • ソート後、学生の名前と成績を表示します。

この応用例では、クラスを使用してデータ構造を定義し、ソートアルゴリズムを適用することで、実際のアプリケーションでのデータ処理を効率化しています。

高度なソートアルゴリズム

基本的なソートアルゴリズムに加えて、より高度なソートアルゴリズムを学ぶことで、特定の状況でより効率的なデータの並べ替えが可能になります。ここでは、ヒープソートとシェルソートという二つの高度なソートアルゴリズムを紹介します。

ヒープソートのアルゴリズム

ヒープソートは、二分ヒープデータ構造を利用したソートアルゴリズムで、常にO(n log n)の計算量を持つ効率的な手法です。

ヒープソートの実装

以下は、C++のクラスを使ったヒープソートの実装例です。

#include <iostream>
#include <vector>

class HeapSort {
public:
    void sort(std::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--) {
            std::swap(arr[0], arr[i]);
            heapify(arr, i, 0);
        }
    }

    void printArray(const std::vector<int>& arr) {
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

private:
    void heapify(std::vector<int>& arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            std::swap(arr[i], arr[largest]);
            heapify(arr, n, largest);
        }
    }
};

int main() {
    std::vector<int> data = {12, 11, 13, 5, 6, 7};
    HeapSort hs;
    std::cout << "Unsorted array: ";
    hs.printArray(data);

    hs.sort(data);
    std::cout << "Sorted array: ";
    hs.printArray(data);

    return 0;
}

シェルソートのアルゴリズム

シェルソートは、間隔を縮めながら要素を比較・交換することで、より効率的なソートを実現します。これは、挿入ソートの改良版とも言えます。

シェルソートの実装

以下は、C++のクラスを使ったシェルソートの実装例です。

#include <iostream>
#include <vector>

class ShellSort {
public:
    void sort(std::vector<int>& arr) {
        int n = arr.size();
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
    }

    void printArray(const std::vector<int>& arr) {
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    std::vector<int> data = {12, 34, 54, 2, 3};
    ShellSort ss;
    std::cout << "Unsorted array: ";
    ss.printArray(data);

    ss.sort(data);
    std::cout << "Sorted array: ";
    ss.printArray(data);

    return 0;
}

実装の解説

  • HeapSortクラスでは、heapifyメソッドを用いて配列をヒープ構造に変換し、ヒープソートを実行します。
  • ShellSortクラスでは、間隔を縮めながら挿入ソートを適用することで、シェルソートを実行します。

これらの高度なソートアルゴリズムを学ぶことで、特定の状況でより効率的なデータソートが可能になります。各アルゴリズムの特性を理解し、適切に選択することが重要です。

ソートアルゴリズムの最適化

ソートアルゴリズムは、適切に最適化することで、パフォーマンスを大幅に向上させることができます。ここでは、一般的な最適化手法と、具体的なアルゴリズムの最適化例について解説します。

一般的な最適化手法

ソートアルゴリズムの最適化には、いくつかの共通の手法があります。

  • キャッシュの活用: データの局所性を高め、キャッシュのヒット率を向上させることで、メモリアクセスの速度を向上させます。
  • 分割統治法の適用: 大きなデータセットを小さく分割し、それぞれを並列処理することで、全体の処理時間を短縮します。
  • 適切なデータ構造の選択: ソート対象のデータに最適なデータ構造を選ぶことで、アルゴリズムの効率を高めます。

バブルソートの最適化例

バブルソートは、最も単純なソートアルゴリズムの一つですが、いくつかの工夫で性能を向上させることができます。

  • 早期終了の導入: 既にソートされている場合に不要な比較を避けるため、交換が行われなかった場合にソートを終了するようにします。
#include <iostream>
#include <vector>

class OptimizedBubbleSort {
public:
    void sort(std::vector<int>& arr) {
        int n = arr.size();
        bool swapped;
        for (int i = 0; i < n - 1; ++i) {
            swapped = false;
            for (int j = 0; j < n - i - 1; ++j) {
                if (arr[j] > arr[j + 1]) {
                    std::swap(arr[j], arr[j + 1]);
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }

    void printArray(const std::vector<int>& arr) {
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    std::vector<int> data = {5, 1, 4, 2, 8};
    OptimizedBubbleSort obs;
    std::cout << "Unsorted array: ";
    obs.printArray(data);

    obs.sort(data);
    std::cout << "Sorted array: ";
    obs.printArray(data);

    return 0;
}

クイックソートの最適化例

クイックソートは非常に効率的なアルゴリズムですが、さらに性能を向上させるための最適化手法があります。

  • メディアン・オブ・スリー法: ピボット選択を改善するために、最初、中間、最後の三つの要素のメディアンをピボットとして選びます。
  • 再帰の最小化: 再帰呼び出しの回数を減らすために、片方の部分リストが十分に小さくなったら挿入ソートに切り替えます。
#include <iostream>
#include <vector>

class OptimizedQuickSort {
public:
    void sort(std::vector<int>& arr) {
        quicksort(arr, 0, arr.size() - 1);
    }

    void printArray(const std::vector<int>& arr) {
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

private:
    void quicksort(std::vector<int>& arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quicksort(arr, low, pi - 1);
            quicksort(arr, pi + 1, high);
        }
    }

    int partition(std::vector<int>& arr, int low, int high) {
        int pivot = medianOfThree(arr, low, high);
        std::swap(arr[pivot], arr[high]);
        int pivotValue = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivotValue) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        return i + 1;
    }

    int medianOfThree(std::vector<int>& arr, int low, int high) {
        int mid = low + (high - low) / 2;
        if (arr[low] > arr[mid]) std::swap(arr[low], arr[mid]);
        if (arr[low] > arr[high]) std::swap(arr[low], arr[high]);
        if (arr[mid] > arr[high]) std::swap(arr[mid], arr[high]);
        return mid;
    }
};

int main() {
    std::vector<int> data = {10, 7, 8, 9, 1, 5};
    OptimizedQuickSort oqs;
    std::cout << "Unsorted array: ";
    oqs.printArray(data);

    oqs.sort(data);
    std::cout << "Sorted array: ";
    oqs.printArray(data);

    return 0;
}

マージソートの最適化例

マージソートは安定性と効率性が高いですが、メモリ使用量が多くなるため、インプレースソートなどの最適化が考えられます。

  • インプレースマージソート: メモリ使用量を削減するために、インプレースでマージ操作を行います。
  • 小さな配列のソートに挿入ソートを使用: マージソート中に小さな配列が出現した場合、より高速な挿入ソートを使用します。

最適化されたソートアルゴリズムは、実際のアプリケーションでの性能向上に大きく寄与します。各アルゴリズムの特性を理解し、適切な最適化手法を適用することが重要です。

実践問題と演習

この記事で学んだソートアルゴリズムの理解を深めるために、いくつかの実践問題と演習を提供します。これらの問題を通じて、ソートアルゴリズムの実装力と応用力を高めることができます。

問題1: 学生の成績管理システムの実装

概要: 学生の成績管理システムを作成し、成績に基づいて学生リストをソートするプログラムを実装します。

要件:

  • 学生クラスには名前、学籍番号、成績を含めます。
  • クラスのメンバーをソートするために、バブルソート、クイックソート、マージソートのいずれかを使用します。
  • ソート後に、成績順に並んだ学生リストを表示します。

サンプルコード:

#include <iostream>
#include <vector>
#include <string>

// 学生クラスの定義
class Student {
public:
    std::string name;
    int id;
    double grade;

    Student(std::string name, int id, double grade)
        : name(name), id(id), grade(grade) {}
};

// クイックソートクラスの定義
class QuickSort {
public:
    void sort(std::vector<Student>& students) {
        quicksort(students, 0, students.size() - 1);
    }

private:
    void quicksort(std::vector<Student>& students, int low, int high) {
        if (low < high) {
            int pi = partition(students, low, high);
            quicksort(students, low, pi - 1);
            quicksort(students, pi + 1, high);
        }
    }

    int partition(std::vector<Student>& students, int low, int high) {
        double pivot = students[high].grade;
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (students[j].grade > pivot) {
                i++;
                std::swap(students[i], students[j]);
            }
        }
        std::swap(students[i + 1], students[high]);
        return i + 1;
    }
};

// メイン関数
int main() {
    std::vector<Student> students = {
        {"Alice", 1001, 85.5},
        {"Bob", 1002, 92.3},
        {"Charlie", 1003, 78.9},
        {"David", 1004, 88.4},
        {"Eve", 1005, 91.2}
    };

    QuickSort sorter;
    sorter.sort(students);

    std::cout << "Students sorted by grade (descending order):" << std::endl;
    for (const auto& student : students) {
        std::cout << student.name << " (" << student.id << "): " << student.grade << std::endl;
    }

    return 0;
}

問題2: 昇順および降順のソート

概要: 与えられた整数配列を昇順および降順にソートするプログラムを実装します。

要件:

  • ユーザーから整数配列を入力として受け取ります。
  • 昇順にソートした結果を出力します。
  • 降順にソートした結果を出力します。

サンプルコード:

#include <iostream>
#include <vector>
#include <algorithm>

void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> data;
    int n, temp;

    std::cout << "Enter number of elements: ";
    std::cin >> n;
    std::cout << "Enter elements: ";
    for (int i = 0; i < n; ++i) {
        std::cin >> temp;
        data.push_back(temp);
    }

    std::vector<int> dataAsc = data;
    std::vector<int> dataDesc = data;

    std::sort(dataAsc.begin(), dataAsc.end());
    std::sort(dataDesc.begin(), dataDesc.end(), std::greater<int>());

    std::cout << "Array sorted in ascending order: ";
    printArray(dataAsc);

    std::cout << "Array sorted in descending order: ";
    printArray(dataDesc);

    return 0;
}

問題3: カスタム比較関数を使用したソート

概要: カスタム比較関数を使用して、文字列の長さに基づいてソートするプログラムを実装します。

要件:

  • ユーザーから文字列の配列を入力として受け取ります。
  • 文字列の長さに基づいてソートした結果を出力します。

サンプルコード:

#include <iostream>
#include <vector>
#include <algorithm>

bool compareByLength(const std::string& a, const std::string& b) {
    return a.length() < b.length();
}

void printArray(const std::vector<std::string>& arr) {
    for (const std::string& str : arr) {
        std::cout << str << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<std::string> data;
    int n;
    std::string temp;

    std::cout << "Enter number of strings: ";
    std::cin >> n;
    std::cout << "Enter strings: ";
    std::cin.ignore(); // 念のため
    for (int i = 0; i < n; ++i) {
        std::getline(std::cin, temp);
        data.push_back(temp);
    }

    std::sort(data.begin(), data.end(), compareByLength);

    std::cout << "Strings sorted by length: ";
    printArray(data);

    return 0;
}

これらの実践問題を通じて、ソートアルゴリズムの理解を深め、実際のプログラムで応用する力を養うことができます。各問題の要件を満たすようにコードを実装し、動作を確認してみてください。

まとめ

本記事では、C++のクラスを用いてソートアルゴリズムを実装する方法と、それぞれの応用例を詳しく解説しました。基本的なバブルソート、クイックソート、マージソートから、より高度なヒープソート、シェルソートの実装と最適化までを網羅し、各アルゴリズムの特性や適用場面についても学びました。さらに、実践問題を通じて、学んだ知識を実際のコードに応用する力を養うことができました。ソートアルゴリズムはデータ処理の基盤となる重要な技術ですので、これらの知識を活用し、さらに深い理解を目指してください。

C++
プログラミング クラス 実装例 ソートアルゴリズム C++

コメント

コメントする

目次