トップページ⇒tech
97コメント24KB

Ｃ言語　バブルソート

■ このスレッドは過去ログ倉庫に格納されています
0001あおい☆彡NGNG
配列に代入された数値を小さい順に並べ変えるプログラムを作りなさい。

ただし、数値は配列numbers[]にすでに代入されているものとし、変数nには代入された数値の個数が代入されているものとする。
（例）
int numbers[10] = { 82, 47, 2, 29, 95, 15, 38, 66, 51, 72 };
int n = 10;
上記のようにすると、その出力は、
2, 15, 29, 38, 47, 51, 66, 72, 82, 95
となる。
↑
バブルソートの問題なんですが全然わかりません！
Ｃ言語わかる人教えてください！
お願いします（＞ｍ＜）
0002デフォルトの名無しさんNGNG
惚れた
0003デフォルトの名無しさんNGNG
>>3
わろた
0004デフォルトの名無しさんNGNG
>>1
ぁぉぃちゃんの年齢、スリーサイズ教えてくれたら
やさしいおにいちゃんが答えてくれるかもよ。
0005あおい☆彡NGNG
>>4
年齢：19
スリーサイズ:上から 76, 58, 81 です。
よろしくお願いします
0006デフォルトの名無しさんNGNG
メモ付き乳もないのに、よく相手してるなおまいら
0007デフォルトの名無しさんNGNG
>>5のようにすると、その出力は、
19, 58, 76, 81
となる。
0008デフォルトの名無しさんNGNG
>>1
単発スレ立てるな。
そういう質問は下のどちらかでしろ。
http://pc5.2ch.net/test/read.cgi/tech/1104114259/
http://pc5.2ch.net/test/read.cgi/tech/1104114259/
0009デフォルトの名無しさんNGNG
>>1
インターネットで調べればいくらでもでてくるだろ
0010デフォルトの名無しさんNGNG
>>1
この辺の勉強はネットより本の方が良いような悪いような
0011デフォルトの名無しさんNGNG
>>1
http://www1.cts.ne.jp/~clab/Contents/Sortindex.html
0012デフォルトの名無しさんNGNG

= = = = = = = = = = = = 終 了 = = = = = = = = = = = = =
0013デフォルトの名無しさんNGNG
>>1
いいことを教えてやろう。
「バルブ」ソートで検索してみな
0014デフォルトの名無しさんNGNG
>>1
2chでお前の宿題をやらせようとしてんじゃねーよｗｗｗｗｗｗ
0015デフォルトの名無しさんNGNG
>>1
バブルソートて実装はものすごく簡単なのに
0016デフォルトの名無しさんNGNG
>>1
松原...?
0017デフォルトの名無しさんNGNG
>>1
bubblesort(&number,n)でいいんじゃね？
0018デフォルトの名無しさんNGNG
>>1
いいことを教えてやろう。
「バイブ ソープ」で検索してみな
0019デフォルトの名無しさんNGNG
#include <stdio.h>

int main(int argc, char **argv){
　int numbers[] = { 82, 47, 2, 29, 95, 15, 38, 66, 51, 72 };
　int n = sizeof(numbers) / sizeof(int);
　int i, j, swap;
　for(i = 1; i < n; i++){
　　for(j = 1; j < i; j++){
　　　if(numbers[j] < numbers[j-1]){
　　　　swap = numbers[j-1];
　　　　numbers[j-1] = numbers[j];
　　　　numbers[j] = swap;
　　　}
　　}
　}
　for(i = 0; i < n; i++){
　　printf("%d\n", numbers[i]);
　}
　return 0;
}
0020デフォルトの名無しさんNGNG
まじめだなあ
0021デフォルトの名無しさんNGNG
>1
問題文中には、特にバブルソートでという指定は無いようだけど、
クイックソートじゃダメ？
0022デフォルトの名無しさんNGNG
age
0023デフォルトの名無しさんNGNG
評価の指標
0:未提出
1:よくわからんけど動いてる
2:バブルソート(車輪の再発明)
3:バブルソート(過去レポ○写し), その他のソート方法
4:クイックソート(計算量に対する処置なし)
5:クイックソート(採点者のお気に入り)
0024デフォルトの名無しさんNGNG
クイックソートは、再帰処理に関する練習問題としてはよく出てくるよね。
あと、ハノイの塔とかも。
0025デフォルトの名無しさんNGNG
>24
むしろフィボなっち
0026デフォルトの名無しさんNGNG
>>19
それバブルソートじゃないし
0027デフォルトの名無しさんNGNG
バブルスターっつったらアレでしょうが
0028デフォルトの名無しさんNGNG
>>26
じゃあなに
0029デフォルトの名無しさんNGNG
さしすせそると
0030デフォルトの名無しさんNGNG
>>24
ハノイの塔を手続き部分無しで書いてください。
0031デフォルトの名無しさんNGNG
　
. |---|
|-----| 　　　　　　 |-|
0032デフォルトの名無しさんNGNG
>>31
BlowJob!
0033デフォルトの名無しさんNGNG
とりあえずだな、

sort()

だけ書いて、後は「２ちゃんねるで誰も教えてくれなかったんです」と言い訳文を書いとけ。
0034デフォルトの名無しさんNGNG
>>1
>スリーサイズは上から60,58,64
まで読んだ

>>19はなんだっけ。
そして下は何だっけ。
int main()
{
　　int numbers[10] = { 82, 47, 2, 29, 95, 15, 38, 66, 51, 72 };
　　int n = 10;
　　int i, j,tmp;
　　for(i=0;i<n;i++)
　　　　for(j=0;j<i;j++)
　　　　　　if(numbers[i]<numbers[j]){
　　　　　　　　tmp = numbers[i];
　　　　　　　　numbers[i] = numbers[j];
　　　　　　　　numbers[j] = tmp;
　　　　　　}

　　for(i=0;i<n;i++)
　　　　printf("%d ",numbers[i]);
　　printf("\n");
　　return 0;
}
0035デフォルトの名無しさんNGNG
微妙に良スレになってきた予感
0036デフォルトの名無しさんNGNG
ここらへんでほえほげ
0037デフォルトの名無しさんNGNG
#include<stdio.h>
#include<string.h>
int main(){
　　int number[10] = { 82, 47, 2, 29, 95, 15, 38, 66, 51, 72 };
　　int n = 10;
　　int i;
　　char *filename=tmpnam(NULL);
　　char pstr[L_tmpnam+24]="sort ";
　　FILE *fp=fopen(filename,"w");
　　FILE *pp;
　　char buffer[256];
　　strcat(pstr,filename);
　　for(i=0;i<n;i++){
　　　　fprintf(fp,"%010d\n",number[i]);
　　}
　　fclose(fp);
　　pp=popen(pstr,"r");
　　while(fgets(buffer,sizeof(buffer),pp)){
　　　　int a;
　　　　sscanf(buffer,"%d",&a);
　　　　printf("%d ",a);
　　}
　　printf("\n");
　　return 0;
}
環境によってはpopenが_popenかも
0038デフォルトの名無しさんNGNG
>>37
sortが標準出力してくれるんだから、popen("sort", "w");でいい。
0039デフォルトの名無しさんNGNG
>>38
それだと>>1みたいな出力に出来ないから
って , を忘れてる orz

あーUNIX系のsortだと-gってのがあるのか
これだと%010dとか不恰好なことしなくてすむなー
0040デフォルトの名無しさんNGNG
>>39
それじゃ、popen("sort -g|awk '{printf(\"%s, \", $0);}'", "w");とかw
0041デフォルトの名無しさんNGNG
バブルソート
選択ソート
挿入ソート
シェルソート
クイックソート
マージソート
あと>>35は何？自己流？
004241NGNG
>>34の間違いであります！
0043デフォルトの名無しさんNGNG
選択ソートっぽいけど
0044デフォルトの名無しさんNGNG
間違えた
ただのバブルソートじゃねーか
0045デフォルトの名無しさんNGNG
一瞬良スレかと思ったが、なかなか低レベルなスレだな。
0046デフォルトの名無しさんNGNG
バイブソープ
0047デフォルトの名無しさんNGNG
>>45
バブルソートではどうやっても高レベルにはならんだろ
0048デフォルトの名無しさんNGNG
バブル時代とそーっと邂逅して懐古するスレということにしてみてはどうか
0049デフォルトの名無しさんNGNG
Cに限らずいろんな言語でバブろうぜ！！！
0050デフォルトの名無しさん05/01/17 23:29:40
for (i = 0; i < n - 1; i++) {
for (j = n - 1; j > i; j--) {
if (x[j - 1] > x[j]) { /* 前の要素の方が大きかったら */
temp = x[j]; /* 交換する */
x[j] = x[j - 1];
x[j - 1]= temp;
}
}
}
0051デフォルトの名無しさん05/01/18 01:36:33



・・・で？
0052デフォルトの名無しさん05/01/18 12:08:47
　 ∧＿∧
　（　´∀｀）
　（　　　　）
　82, 47, 2, 29, 95, 15, 38, 66, 51, 72

　 ∧＿∧
　（　´∀｀）
　（　つ82）
　　 47, 2, 29, 95, 15, 38, 66, 51, 72

　　　 ∧＿∧
　　　（　´∀｀）
　　　（　つ82つ95
　　 47, 2, 29, 　 15, 38, 66, 51, 72

　　　　　　　　　　　　　　　　　　 ∧＿∧
　　　　　　　　　　　　　　　　　　（　´∀｀）　／
　　　　　　　　　　　　　　　　　　（　つ　　つ
　　 47, 2, 29, 　 15, 38, 66, 51, 72, 82, 95　─
　　　　　　　　　　　　　　　　　　　　　/'　ヽ＼

　　　　　　　　　　　　　　　　 ｷﾞｭｯ 　 ∧＿∧
　　　　　　　　　　　　　　　　　　　　 （´∀｀　）　≡≡
47, 2, 29, 15, 38, 66, 51, 72, 82, 95⊂　　　）
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
0053デフォルトの名無しさん05/01/18 13:11:19
その ｷﾞｭｯ 　 がコンピュータでは高コストなわけだよ
0054デフォルトの名無しさん05/01/19 02:53:15
データ構造によるがな
0055デフォルトの名無しさん05/01/19 09:56:22
双方向連結リスト
0056名無しのゴンベイ05/01/21 10:13:45
バブルソートを使ったプログラムをお願いします。
0057デフォルトの名無しさん05/01/23 00:57:52
>>5
正月早々惚れた！
0058デフォルトの名無しさん05/01/23 02:11:42
おそっｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
0059デフォルトの名無しさん05/01/30 00:47:22
バブル期入社の人のためによく使われる手法です。
0060デフォルトの名無しさん05/01/30 20:50:30
>>59
バブル期入社組が一番上にくるんだよな。

（ここだけの話だけど、リストラの優先順位らしいぜ）
0061デフォルトの名無しさん05/01/31 03:16:36
終了条件って収束するまで？
0062デフォルトの名無しさん05/01/31 03:20:10
>>61
前のﾙｰﾌﾟで一度も交換がなかったらでは?
0063デフォルトの名無しさん05/01/31 03:49:32
それ収束って言うよね？
00646205/01/31 04:02:12
ああ、そうか。すまん。
0065C#05/01/31 11:48:39
C# こんな感じ？
public class Sorter {
private int[] data;
//ry
public void BubbleSort() {
for (int i=0; i<data.Length; i++) {
for (int j=1; j<data.Length; j++) {
if ( data[j-1] > data[j] ){
Swap(ref data[j], ref data[j-1]);
}
}
}
}
// ry
private void Swap(ref int a, ref int b){
int tmp = a;
a = b;
b = tmp;
}

// ry
0066デフォルトの名無しさん05/02/01 09:43:00
※
 ○
Ｏ
 o
｡
0067デフォルトの名無しさんNGNG
>>1
某大学で同じ宿題が出たぞ
0068デフォルトの名無しさん05/02/01 20:28:13
>>67
なんでID付いてんの？
0069デフォルトの名無しさん05/02/01 20:43:49
>>68
beカテゴリーの板にログインしてんじゃないのかな

面白ネタnews板
http://be.2ch.net/be/
0070デフォルトの名無しさん05/02/01 20:46:37
>>69
その板文字コードおかしいーーーって、マジで。
ありえねーッ
0071デフォルトの名無しさん05/02/03 15:32:26
つ[numbers = numbers[0..n].sort;]
0072デフォルトの名無しさん05/02/13 17:40:56
配列の動きをレポートしてくる宿題でわからないところがあったので教えてください。

マージソートでデータ（乱数１〜１０）を10用意してソートしたときの配列の動き方がわかりません。
データが１つになるまで分割するまではわかるのですが、
2回目のマージで個数が　　
２・２・２・２・２　になって
３回目のマージで
２・２・２・２・２　が　４・４・２　になると思うのですが、一番最後の２はそのまま残して次のマージで結合するのでしょうか？

いろいろなサイトを見て回ったのですが要素が８個のとこばかりでよくわかりませんでした。
マージの板がなかったのでここで質問してしまいました、よろしくお願いします。
0073デフォルトの名無しさん05/02/13 19:10:21
中学生の技術科の問題？
0074デフォルトの名無しさん05/02/13 19:10:24
C言語なら俺に聞け!Part 102
http://pc5.2ch.net/test/read.cgi/tech/1108056236/

このスレで聞いたほうが早いと思う
0075デフォルトの名無しさん05/02/14 07:35:21
各回のﾏｰｼﾞで塊が偶数個になるように0を追加する。
2･2･2･2･2(･0)
4･4･2(･0)
8･2
10
遡って始めから6個の0を追加して16個にして考えてもよい。
0076デフォルトの名無しさん05/02/17 13:29:14
丁寧にやらなきゃダメだよ
ソーっとね。 ソートだけに。

ﾌﾟｹﾞﾗ
0077デフォルトの名無しさん05/02/17 18:08:04
昔、バブルソートの変形で、Qソートより速いってのを見た覚えがあるんだけど、
誰か知らない？
0078(´･ω･`)知らんがな05/02/17 18:45:45
>>77
(´･ω･`)知らんがな
昔､挿入ｿｰﾄの変形で､要素数が少なければ結構速いShellｿｰﾄってのを見た覚えがあるけんど､誰か知らんか?
0079デフォルトの名無しさん05/02/17 21:03:37
>>77
コムソート
0080(´･ω･`)知らんがな05/02/17 21:27:20
>>79
ほぼO(n･log n)だがｸｲｯｸｿｰﾄより遅くﾋｰﾌﾟｿｰﾄと同じくらい｡
ﾃﾞｰﾀの並びによってはひどく遅くなることがある｡
0081デフォルトの名無しさん05/02/18 16:47:13
バケツソート
00827905/02/18 18:34:36
あ、qソートより速いって事は無かったはず
昔とあるBBSでえらい速いバブルソートとして紹介されてた様な
0083デフォルトの名無しさん05/02/18 22:47:25
>>77
日経バイトに載っていたやつかな？

クイックソートは名前ほど速くない。
0084デフォルトの名無しさん05/02/18 23:03:18
ジェフスコットソート
0085デフォルトの名無しさん05/02/18 23:44:53
標準関数のqsortの中身はｸｲｯｸｿｰﾄかﾏｰｼﾞｿｰﾄで決まりでしょう?
配列の汎用ｿｰﾄはもういいや｡
単方向ﾘｽﾄのｿｰﾄで配列に移し替えない早いやつを希望…ってｽﾚ違いか…残念無念
0086デフォルトの名無しさん05/02/18 23:52:50
クイックソートはアルゴリズム書くなんて面倒なことしなくても実装されてるんで使うのに必要な手間がクイック
0087デフォルトの名無しさん05/02/19 00:00:00
>>86
でもC言語の規格上はqsortはｸｲｯｸｿｰﾄでなくてもOKなはず｡
中身はどうであれ､十分速ければ無問題｡
0088デフォルトの名無しさん05/02/24 11:24:55
>>85
リストは quick sort が楽だよ。
閾値の上、下、等しいの3つに破壊的に(tail / next/ cdr 部分書き換えの)イモ刺しで分割して、
これまた破壊的に接続する。
consセルも消費しないし、stableで使いやすい。非破壊にするなら最初にコピーしとく。
00898505/02/24 12:24:06
>>88
ありがとう。
昨日、最悪の場合でもO(n･log n)でないといけなくなって、自然ﾏｰｼﾞｿｰﾄで作ってしまいました。
付け替えが多くやや遅いようです。

ﾘｽﾄ版 quick sort の閾値の選び方も配列版と同じくらい種類がありそうですね｡
平均的にはﾘｽﾄ版 quick sortの方が速そう。
0090デフォルトの名無しさん05/02/28 02:50:54
int i = 1;
while( i < n )
{
if( data[i-1] <= data[i] || i == 0 ) i++;
else
{
int temp = data[i];
data[i] = data[i-1];
data[i-1] = temp;
i--;
}
}
妖精ソートとか使って意表をついてみようぜ。
バブルソート並みの速度だが
0091デフォルトの名無しさん2005/06/05(日) 03:25:05
void SimpleInsertion(int data[], int n){
　 int tmp, i, j;
　 for( j=1; j < n; j++ ){
　 i = j - 1;
　 tmp = data[j];
　 while( (i>=0) && (tmp<data[i]) ){
　 data[i+1] = data[i];
　 i = i - 1;
　 }
　 data[i+1] = tmp; // これが無いと失敗する場合の配列を教えて！！
　 }
}
0092デフォルトの名無しさん2005/06/05(日) 03:28:45
ここではそれをやってない
http://www.geocities.co.jp/SiliconValley/4334/unibon/asp/vbscriptsort.html
Sub sortInsertion(ByRef a) ' 挿入ソート
Dim i
For i = 1 To UBound(a)
Dim j
For j = i To 1 Step -1
If a(j).compareTo(a(j - 1)) < 0 Then
Call swap(a(j), a(j - 1))
Else
Exit For
End If
Next
Next
End Sub
0093デフォルトの名無しさん2005/06/05(日) 03:39:49
http://www.sra.co.jp/people/miyata/algorithm/inssort.txt
ここも、最後の
a[j + 1] = x;
って意味あるんですか？
0094デフォルトの名無しさん2005/06/05(日) 04:14:33
modal sortが最強だろ
0095デフォルトの名無しさん2005/06/05(日) 04:42:19
>>91-93
試してから質問してるかぁ？それが無かったらソートにならんだろ。

ヒント:
91>data[i+1] = data[i]; と
92>Call swap(〜
の違いを考えよう。
0096デフォルトの名無しさん2005/06/12(日) 13:55:45
データをひとつづつ読み取りながら、コンテナに格納していく場合、挿入ソートが最強。
ランダムな値に対しては、qsortが有効だから、この二つのソートでたいていは間に合う。
0097デフォルトの名無しさん2005/07/15(金) 14:26:15
おれは基数ソート。キーが数字じゃないとできんという欠点はあるが
とりあえず最強
■ このスレッドは過去ログ倉庫に格納されています