前回に引き続き今回はマージソートについてです
-
-
バブルソートを理解する - ナストンのまとめ
前回に引き続き今回はバブルソートについてです バブルソートって？ ソートアルゴリズムの1つで、処理時間が遅いものとなりま ...
nasuton.net
マージソートって？
クイックソートと同じく処理が速いものとなりますが、ソート時に複数の配列を作成する必要があるため、メモリを消費するという難点があります。詳しくは以下のサイトがわかりやすいと思います
-
-
https://www.tomotaku.com/merge-sort-algorithm
続きを読む
マージソートを実装する
ランダム配列は前回の記事で作成したものを使用します。それでは実際にマージソートをC＋＋で実装してみます
template <typename T>
void mergeSort(std::vector<T>& 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);
}
}まずは再帰的に呼び出す関数を用意します。配列の入れ替えを実施する関数は別で用意します
template <typename T>
void merge(std::vector<T>& arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
// 一時的なベクターを作成
std::vector<T> leftArray(n1);
std::vector<T> rightArray(n2);
// 左半分を一時的なベクターにコピー
for (int i = 0; i < n1; i++) {
leftArray[i] = arr[left + i];
}
// 右半分を一時的なベクターにコピー
for (int j = 0; j < n2; j++) {
rightArray[j] = arr[middle + 1 + j];
}
// マージ
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++;
}
}最期に配列の中身を入れ替える関数を実装します
実際に動かしてみる
検証用の配列を作成し、それをマージソートで並び替えて結果を見てみましょう
std::vector<int> arr = RandomCreate();
int size = arr.size();
std::cout << "Original Array: ";
for (int i : arr) {
std::cout << i << " ";
}
std::cout << std::endl;
mergeSort(arr, 0, size - 1);
std::cout << "Sorted Array: ";
for (int i : arr) {
std::cout << i << " ";
}
std::cout << std::endl;
マージソートを用いて配列が並び変えられていることが確認できました
会社紹介
私が所属しているアドバンスド・ソリューション株式会社(以下、ADS)は一緒に働く仲間を募集しています
会社概要
「技術」×「知恵」＝顧客課題の解決・新しい価値の創造
この方程式の実現はADSが大切にしている考えで、技術を磨き続けるgeekさと、顧客を思うloveがあってこそ実現できる世界観だと思っています
この『love & geek』の精神さえあれば、得意不得意はno problem！
技術はピカイチだけど顧客折衝はちょっと苦手。OKです。技術はまだ未熟だけど顧客と知恵を出し合って要件定義するのは大好き。OKです
凸凹な社員の集まり、色んなカラーや柄の個性が集まっているからこそ、常に新しいソリューションが生まれています
ミッション
私たちは、テクノロジーを活用し、業務や事業の生産性向上と企業進化を支援します
-
-
アドバンスド・ソリューション株式会社
アドバンスド・ソリューションは主にMicrosoft製品を使用して、企業の生産性向上に取り組んでいます。要件定義から導入 ...
サイトへ移動
-
-
お問い合わせ | アドバンスド・ソリューション株式会社
お問い合わせはこちら
