僕が作ったプログラムで、これはバブルソートなのかわからないので教えてください。
また、ほかのソートの仕方も教えてください。
よろしくお願いします。
汎用関数を使っているのでわかりにくいかもしれないですがお願いします。
#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.1
- 回答日時:
バブルソートといいます。
内側のループを抜けると一番小さなものがdata[0]に確定しますよね。
次は2番めに小さなものがdata[1]に確定します。
data[]を上からdata[0]、data[1]・・・と並べてこの状態を見ていると
泡(data[i])が下から沸き上がってくるようにみえることからこの名が付いています。
このソートはデータが倍になると4倍、3倍になると9倍の時間がかかります。
わかりやすいですがデータ量が多いと遅いソートです。
早いのはクイックソート。これはデータ量が倍になっても2倍、
3倍になっても3倍の時間しかかかりません。
その代わり、プログタラムは複雑でわかりにくいものとなります。
その中間、わかりやすくて早いのがシェルソートです。
No.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);
}
ありがとうございます。
ヘッダーファイルを使ったソートはわかるのですが、内部でどのような動作をしているのかわからなかったので、ソートアルゴリズムを勉強中で質問させていただきました。
No.4ベストアンサー
- 回答日時:
バブルソートではないですね。
http://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96% …
選択ソートではないかと思います。
http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E% …
> また、ほかのソートの仕方も教えてください。
「ソート アルゴリズム」などで検索するといっぱい見つかると思います。
他の回答である通り、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]);
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# 10個の実数に対する降順ソート結果を出力するプログラムを作りたいのですが、以下のプログラムをどう直せ 1 2022/07/09 22:16
- C言語・C++・C# c言語の問題です 課題1 (二分探索木とセット) 大きさ size の配列 array を考える。す 2 2023/01/10 21:08
- C言語・C++・C# C++初心者です stirng 2 2022/09/20 20:43
- C言語・C++・C# C++プログラミングコードにポリモーフィズムを取り入れ方を教えてください。 2 2023/06/09 11:17
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
- C言語・C++・C# C++のcinの動作 5 2023/02/26 00:13
- C言語・C++・C# このプログラミング誰か教えてくれませんか 1 2022/06/02 15:27
- C言語・C++・C# c言語配列の結合についてです。 なぜうまくいかないのでしょうか。 #include <stdio.h 4 2022/05/30 22:42
- C言語・C++・C# 宣言する関数の形が決まっている状態で、 str1とstr2の文字列をこの順に引っ付けてstrに保存し 2 2022/05/30 18:21
- C言語・C++・C# C#テキストボックスの文字を配列にいれてその後表示する 4 2022/07/17 04:47
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
ファイル名「1.jpg ~10.jpg~...
-
VB.NETでファイル名順にファイ...
-
System.IO.Directory.GetFiles...
-
(VBA) Dir 関数で取得するファ...
-
数字文字列のソート方法
-
n番目に大きい数を求めるアル...
-
Excelですべての組合せ(重複組...
-
リスト構造のソートで悩んでま...
-
自己参照型構造体とソート
-
C#のリストボックスで、クリッ...
-
配列
-
VBScriptで重複レコードを削除...
-
excel VBA の条件をつけての列...
-
C# DataGridView のヘッダーセ...
-
DataGridViewでのソート制御
-
C言語 配列の長さの上限
-
セグメントエラー
-
関数から配列を返すには?
-
VBAのプログラムで、DIAG = 1# ...
-
16進数を2文字ずつ配列に格納し...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
VB.NETでファイル名順にファイ...
-
ファイル名「1.jpg ~10.jpg~...
-
リスト構造のソートで悩んでま...
-
excel VBA の条件をつけての列...
-
C# DataGridView のヘッダーセ...
-
DataGridViewの複数列を連動し...
-
文字列をソートする方法
-
C言語・要素除去
-
C# DataTableの行をソートしてD...
-
Excelですべての組合せ(重複組...
-
VBA基本構文の作り方 2列の...
-
列のどこをクリックしてもソー...
-
excel VBA リストビューの行...
-
あるディレクトリ内のファイル...
-
コレクションの数値をSortで並...
-
数字文字列のソート方法
-
VBScriptで重複レコードを削除...
-
2次元配列を複数項目でソートし...
-
10個の整数を入力して小さい順...
おすすめ情報