こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

C++ ソートのやり方

僕が作ったプログラムで、これはバブルソートなのかわからないので教えてください。
また、ほかのソートの仕方も教えてください。
よろしくお願いします。

汎用関数を使っているのでわかりにくいかもしれないですがお願いします。

#include <iostream>
using namespace std;

template <class X>void Sort(X *data, int size)
{
X temp;

for (int i = 0; i < size; i++){
for (int j = i + 1; j < size; j++){
if (data[i]>data[j]){
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
}

int main()
{
int i[10]{1, 4, 3, 5, 2, 10, 2, 7, 6, 8};
char c[10]{'c', 'b', 'z', 'a', 'x', 'y', 'j', 'n', 'm', 'r'};

Sort(c, 10);
Sort(i, 10);

for (int j = 0; j < 10; j++){
cout << i[j] << ' ';
}
cout << endl;

for (int j = 0; j < 10; j++){
cout << c[j] << ' ';
}
cout << endl;


getchar();
return 0;
}

投稿日時 - 2014-08-15 23:15:06

QNo.8718289

困ってます

質問者が選んだベストアンサー

バブルソートではないですね。
http://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88

選択ソートではないかと思います。
http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88


> また、ほかのソートの仕方も教えてください。

「ソート アルゴリズム」などで検索するといっぱい見つかると思います。
他の回答である通り、C++でプログラムを書くとしたら、std::sortを使うのが普通です。今回は勉強のために自分で書いてみているのでしょうけれど。

quick sortとか?
template <typename T>
void Swap(T& i0, T& i1) {
T tmp = i0;
i0 = i1;
i1 = tmp;
}

template <typename BiderectIter>
void QuickSort(BiderectIter begin, BiderectIter end)
{
typedef typename std::iterator_traits<BiderectIter>::value_type value_type;
if (begin < end) {
BiderectIter pivot_index = end - 1;
value_type pivot_value = *(end - 1);
BiderectIter store_index = begin;
for (BiderectIter it = begin; it != end - 1; it++) {
if (*it < pivot_value) {
Swap(*it, *store_index);
store_index++;
}
}
Swap(*store_index, *pivot_index);
QuickSort(begin, store_index);
QuickSort(store_index + 1, end);
}
}

merge sortとか?
template <typename Iter>
void Merge(Iter begin, Iter middle, Iter end)
{
typedef typename std::iterator_traits<Iter>::value_type type;
std::vector<type> tmp;
tmp.reserve(end - begin);
Iter fhead = begin, lhead = middle;
while (fhead != middle && lhead != end) {
if (*fhead < *lhead) {
tmp.push_back(*fhead);
fhead++;
} else {
tmp.push_back(*lhead);
lhead++;
}
}
if (fhead == middle) {
for (; lhead != end; lhead++) {
tmp.push_back(*lhead);
}
}
if (lhead == end) {
for (; fhead != middle; fhead++) {
tmp.push_back(*fhead);
}
}

Iter it = begin;
for (size_t i = 0; i < tmp.size(); i++) {
*it++ = tmp[i];
}
}

template <typename Iter>
void MergeSort(Iter begin, Iter end)
{
size_t size = end - begin;
if (size < 2)
return;

Iter middle = begin + size / 2;
MergeSort(begin, middle);
MergeSort(middle, end);
Merge(begin, middle, end);
}


呼び出し方はこんな感じになりますが。
QuickSort(&c[0], &c[10]);
MergeSort(&i[0], &i[10]);

投稿日時 - 2014-08-16 10:48:00

お礼

ありがとうございました。
色々なソートのアルゴリズムも答えてくれてありがとうございました。

投稿日時 - 2014-08-16 21:19:06

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(4)

ANo.3

ふつう, バブルソートというと「隣接する要素を比較する」ものを指すはずだから, これは「バブルソート」とはみなさないんじゃないかな.

どちらかというと, 無駄にいっぱい交換をする選択ソートって感じ.

投稿日時 - 2014-08-15 23:51:50

お礼

回答ありがとうございました。

投稿日時 - 2014-08-16 21:16:26

ANo.2

バブルではなさそう。

バブルソートは
「i 番目 と i+1番目を比較し、逆順なら入れ替える」
を繰り返します。比較/交換を隣同士で行うのがバブルソートです。

> ほかのソートの仕方も教えてください。

#include <algorithm>

int main() {
int i[10]{1, 4, 3, 5, 2, 10, 2, 7, 6, 8};
char c[10]{'c', 'b', 'z', 'a', 'x', 'y', 'j', 'n', 'm', 'r'};

std::sort(i, i+10);
std::sort(c, c+10);
}

投稿日時 - 2014-08-15 23:51:14

お礼

ありがとうございます。
ヘッダーファイルを使ったソートはわかるのですが、内部でどのような動作をしているのかわからなかったので、ソートアルゴリズムを勉強中で質問させていただきました。

投稿日時 - 2014-08-16 21:17:48

ANo.1

バブルソートといいます。

内側のループを抜けると一番小さなものがdata[0]に確定しますよね。
次は2番めに小さなものがdata[1]に確定します。

data[]を上からdata[0]、data[1]・・・と並べてこの状態を見ていると
泡(data[i])が下から沸き上がってくるようにみえることからこの名が付いています。

このソートはデータが倍になると4倍、3倍になると9倍の時間がかかります。
わかりやすいですがデータ量が多いと遅いソートです。

早いのはクイックソート。これはデータ量が倍になっても2倍、
3倍になっても3倍の時間しかかかりません。
その代わり、プログタラムは複雑でわかりにくいものとなります。

その中間、わかりやすくて早いのがシェルソートです。

投稿日時 - 2014-08-15 23:26:19

お礼

回答ありがとうございました。

投稿日時 - 2014-08-16 21:18:11