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;
}

回答No.4

hanabutako · ベストアンサー

バブルソートではないですね。
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]);

お礼

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

回答No.3

Tacosan

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

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

お礼

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

回答No.2

επιστημη（@episteme）

バブルではなさそう。

バブルソートは
「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);
}

お礼

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

回答No.1

maiko0318

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

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

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

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

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

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

お礼

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