LoginSignup
3
3

More than 5 years have passed since last update.

@uchida106(tohru uchida)

C++でバブルソート

Last updated at Posted at 2017-08-06

修正履歴

2017/08/09 加筆修正

  • コメントでご指摘を頂いた点につきまして処理を修正
  • 参考追加

2017/9/2 加筆修正

  • コメントのご指摘を頂き、悩みながらゆったりと処理を再度修正
  • 参考追加

はじめに

初投稿となります。
最近C++を始めたばかりで、勉強がてらC++でバブルソートを実施してみます。

バブルソートについて

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。
隣り合う要素の大小を比較しながら整列させること。
最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。
安定な内部ソート。
基本交換法、隣接交換法ともいう。
(単に交換法と言う場合もある)

Wikipedia https://ja.wikipedia.org/wiki/バブルソート

処理を組んでみる

[ 実装例 ]

▼▼▼ ボツ ▼▼▼

ありがたいご指摘をいただき、
以下の理由よりあまりよろしくない処理であると判断しました。

1. グローバル変数？ ありえなーい(爆
2. 要素の入れ替え方法は std::swap の方がスマート
3. 乱数値を取得するには <random> ヘッダを使用した方が良い

↓ ボツ処理内容 ↓

bubbleSort.cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void bubbleSort();
void initRand();
void initArray();
void showArray();

const int ARRAY_SIZE = 10;  // 配列の要素数
const int MAX_NUMBER = 99;  // ソートする要素の最大値
int ARRAY[ARRAY_SIZE];      // 配列設定

int main() {
  // 乱数種を設定
  initRand();
  // ソートする要素をランダムに設定する
  initArray();

  // 初期データの表示
  cout << "[INIT DATA]" << endl;
  showArray();
  cout << endl << endl;

  // バブルソート実施
  cout << "[BUBBLE SORT]" << endl;
  bubbleSort();

  return 0;
}

// バブルソート
void bubbleSort() {
  int tmp;    // 一時格納用
  // ソートを実施
  for(int i = 0; i < ARRAY_SIZE; i++) {
    for(int j = ARRAY_SIZE - 1; j > i; j--) {
      // 隣り合う要素を比較
      if(ARRAY[j] < ARRAY[j - 1]) {
        // 要素を入れ替え
        tmp = ARRAY[j];
        ARRAY[j] = ARRAY[j - 1];
        ARRAY[j - 1] = tmp;
      }
    }
    // 入れ替え状況確認
    showArray();
    cout << "(" << i + 1 << "回目の変更結果)" << endl;
  }
}

// 乱数種の設定
void initRand() {
  srand((unsigned int)time(NULL));
}

// ソートする要素をランダムに設定する
void initArray() {
  for(int i = 0; i < ARRAY_SIZE; i++) {
    ARRAY[i] = rand() % MAX_NUMBER + 1;
  }
}

// 配列要素の表示
void showArray() {
  for(int i = 0; i < ARRAY_SIZE; i++) {
    cout << ARRAY[i] << ' ';
  }
}

▼▼▼ 修正 -> ボツ再び ▼▼▼

1. グローバル変数を削除し、配列は引数で渡すように修正
2. 要素の入れ替えで std::swap を使用
3. <random> ヘッダを使用して乱数値を取得

再度ありがたいご指摘を頂きました。
以下の理由よりダメダメであると判断しました。

1. イテレータを使用することで、一様なデータ処理を書くことができる
2. イテレータを使用すれば、要素のアドレスが連続している必要がない(完全に理解できてはないけど、大きな利点となる？
3. 動的配列 vector を使用した方が色々と便利
4. MinGW GCC で random_device を使用すると毎度同じ値を返すので使用は非推奨
5. クラス・関数は部品である！ブラックボックスな感じで内容を意識することなく使用できるようにすべし(むずかしいぃ、、、

↓ ボツ処理内容 ↓

bubbleSort_2.cpp
#include <iostream>
#include <utility>
#include <random>
using namespace std;

void bubbleSort(int*);
void initArray(int*);
void showArray(const int*);

const int ARRAY_SIZE = 10;   // 配列の要素数
const int MIN_NUMBER = 0;    // ソートする要素の最小値
const int MAX_NUMBER = 99;   // ソートする要素の最大値

int main() {
  int arr[ARRAY_SIZE];

  // ソートする要素をランダムに設定する
  initArray(arr);

  // 初期データの表示
  cout << "[INIT DATA]" << endl;
  showArray(arr);
  cout << endl << endl;

  // バブルソート実施
  cout << "[BUBBLE SORT]" << endl;
  bubbleSort(arr);

  return 0;
}

// バブルソート
void bubbleSort(int* arr) {
  // ソートを実施
  for(int i = 0; i < ARRAY_SIZE; i++) {
    for(int j = ARRAY_SIZE - 1; j > i; j--) {
      // 隣り合う要素を比較
      if(arr[j] < arr[j - 1]) {
        // 要素を入れ替え
        swap(arr[j], arr[j - 1]);
      }
    }
    // 入れ替え状況確認
    showArray(arr);
    cout << "(" << i + 1 << "回目の変更結果)" << endl;
  }
}

// ソートする要素をランダムに設定する
void initArray(int* arr) {
  random_device seed;                                         // 初期シードを乱数で指定
  mt19937 mt(seed());                                         // 擬似乱数の設定
  uniform_int_distribution<> rnd_val(MIN_NUMBER, MAX_NUMBER); // 一様分布乱数の指定

  // 配列にランダムな値を設置
  for(int i = 0; i < ARRAY_SIZE; i++) {
    arr[i] = rnd_val(mt);
  }
}

// 配列要素の表示
void showArray(const int* arr) {
  for(int i = 0; i < ARRAY_SIZE; i++) {
    cout << arr[i] << ' ';
  }
}

▼▼▼ 再度修正 ▼▼▼

1. vector を使用
2. iterator を使用
3. random_device は非推奨なので使用しない
4. 乱数の seed 値を時間から取得するように戻す(他にも良い方法がありそうなものだけれども、、、
5. 関数の中身はそこで全て完結できるように意識する
bubbleSort_3.cpp
#include <iostream>
#include <utility>
#include <ctime>
#include <random>
using namespace std;

void bubbleSort(vector<int>::iterator first, vector<int>::iterator last);
void initArray(vector<int>::iterator first, vector<int>::iterator last, int max = 0, int min = 0);
void showArray(vector<int>::const_iterator first, vector<int>::const_iterator last);

int main() {
  vector<int> vec(10, 0);

  // ソートする要素をランダムに設定する
  initArray(vec.begin(), vec.end(), 99);

  // 初期データの表示
  cout << "[INIT DATA]" << endl;
  showArray(vec.begin(), vec.end());
  cout << endl << endl;

  // バブルソート実施
  cout << "[BUBBLE SORT]" << endl;
  bubbleSort(vec.begin(), vec.end());

  return 0;
}

// バブルソート
void bubbleSort(vector<int>::iterator first, vector<int>::iterator last) {
  int count = 0;
  // ソートを実施
  for(auto e = first; e != last; ++e) {
    for(auto i = last - 1; i != e; --i) {
      auto j = i;
      advance(j, -1);
      if(*i < *j) {
        iter_swap(i, j);
      }
    }
    showArray(first, last);
    cout << "(" << count + 1 << "回目の変更結果)" << endl;
    ++count;
  }
}

// ソートする要素をランダムに設定する
void initArray(vector<int>::iterator first, vector<int>::iterator last, int max, int min) {
  mt19937 mt(static_cast<unsigned int>(time(nullptr)));       // 擬似乱数の設定
  uniform_int_distribution<> rnd_val(min, max);               // 一様分布乱数の指定

  // 値を設置
  for(auto e = first; e != last; ++e) {
    *e = min < max ? rnd_val(mt) : mt();
  }
}

// 配列要素の表示
void showArray(vector<int>::const_iterator first, vector<int>::const_iterator last) {
  for(auto e = first; e != last; ++e) {
    cout << *e << ' ';
  }
}

[ 実行例 ]

[INIT DATA]
97 43 91 23 87 22 15 46 51 44

[BUBBLE SORT]
15 97 43 91 23 87 22 44 46 51 (1回目の変更結果)
15 22 97 43 91 23 87 44 46 51 (2回目の変更結果)
15 22 23 97 43 91 44 87 46 51 (3回目の変更結果)
15 22 23 43 97 44 91 46 87 51 (4回目の変更結果)
15 22 23 43 44 97 46 91 51 87 (5回目の変更結果)
15 22 23 43 44 46 97 51 91 87 (6回目の変更結果)
15 22 23 43 44 46 51 97 87 91 (7回目の変更結果)
15 22 23 43 44 46 51 87 97 91 (8回目の変更結果)
15 22 23 43 44 46 51 87 91 97 (9回目の変更結果)
15 22 23 43 44 46 51 87 91 97 (10回目の変更結果)

雑話

bubbleSort.cppでは色々と書いているけど、今回の主題はbubbleSort関数の中身。
処理の内容としては、配列の要素を総当りで比較しているだけ。
単純なソート方法だったので分かり易かったと思う。

参考

2017/8/9 追加

2017/9/2 追加

3
3
9

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
3