C言語におけるボゴソート

ボゴソートなる量子コンピュータにおいては優秀なソートとなる可能性があるソートがあるらしいのでリハビリがてら実装してみることにした。

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  int array[10];  // 配列
  int t;  // 格納変数
  int i;  // 反復変数
  int size; // 入力数
  int f;  // 条件変数
  int r1,r2;  // ランダム
  
  size = 0;  // 入力数の初期化
  
  while( 1 ) {  // -1が出るまで入力
    scanf("%d",&t);
    if( t == -1 ) { break; }
    array[size] = t;
    size++;
  }
  
  while( 1 ) {  // ボゴソート
    f = 0;  // 条件の初期化
    for( i=0; i<size-1; i++ ) {
      if( array[i] > array[i+1] ) {
        f = 1;
      }
    }
    if( f ) { // ランダムに入れ替える
      r1 = (int)((rand()/(RAND_MAX+1.0))*size);
      r2 = (int)((rand()/(RAND_MAX+1.0))*size);
      
      t = array[r1]; 
      array[r1] = array[r2];
      array[r2] = t;
    } else {
      break;
    }
  }
  
  for( i=0; i<size; i++ ) { // 列挙
    printf("%d ",array[i]);
  }
  
  return 0;
}

でたらめに交換していくようだ。
調べると無限の猿定理とか出てきて奥深い...???
でたらめに交換していくという単純なソートなので覚えていても損はない？(実用的ではないが)

2015.05.01 乱数が適当すぎるので修正

C言語における３つのソートの時間計測

先日の３つのソートの時間計測をしてみた。
計測方法は

#include <time.h>
clock_t start,end;
(冒頭) start = clock();
(最後) end = clock();
       printf("%.2f\n",(double)(end-start)/CLOCKS_PER_SEC);

を用いる。
入力は

10 9 8 7 6 5 4 3 2 1 -1

である。

バブルソート

9.42

選択ソート

6.28

挿入ソート

5.79

一般的に言われるように処理時間は
バブルソート>選択ソート>挿入ソート
となった。

C言語における挿入ソート

ほぼコピペだが実装。

#include <stdio.h>

int main(void)
{
  int array[10];  // 配列
  int t;  // 格納変数
  int k1,k2,k3;  // 反復変数
  
  k1 = 0;  // 反復変数の初期化
  
  while( 1 ) {  // -1が出るまで入力
    scanf("%d",&t);
    if( t == -1 ) break;
    array[k1] = t;
    k1++;
  }
  
  for( k2=1; k2<k1; k2++ ){ //挿入ソート
    t = array[k2];
    for( k3=k2; k3>0 && array[k3-1]>t; k3-- ){
      array[k3] = array[k3-1];
    }
    array[k3] = t;
  }
  
  for( k2=0; k2<k1; k2++ ){ // 列挙
    printf("%d ",array[k2]);
  }
  
  return 0;
}

挿入ソートは条件が合致すれば要素を前に挿入して残りを後ろに押し出していくイメージだろうか。

かなり単純になった。

C言語におけるバブルソート

ほぼコピペだがバブルソートを実装してみた。

#include <stdio.h>

int main(void)
{
  int array[10];  // 配列
  int t;  // 格納変数
  int k1,k2,k3;  // 反復変数
  
  k1 = 0;  // 反復変数の初期化
  
  while( 1 ) {  // -1が出るまで入力
    scanf("%d",&t);
    if( t == -1 ) break;
    array[k1] = t;
    k1++;
  }
  
  for( k2=0; k2<k1-1; k2++ ){
    for( k3=k1-1; k3>k2; k3-- ){
      if( array[k3-1] > array[k3] ){
        t = array[k3];
        array[k3] = array[k3-1];
        array[k3-1] = t;
      }
    }
  }
  
  for( k2=0; k2<k1; k2++ ){ // 列挙
    printf("%d ",array[k2]);
  }
  
  return 0;
}

選択ソートが前から攻めていくイメージならバブルソートは後ろから前から挟んでいくというイメージだろうか。
変数が3つ減ったので単純になった。

とりあえずよくわからない。

C言語における選択ソート

昨日某先輩から「入力された１０個以内の数字を小さい順に並び替える」という問題が出題されたので解いてみた。

#include <stdio.h>

int main(void)
{
  int array[10];  // 配列
  int t;  // 格納変数
  int min,min_pos;  // 一時変数
  int k1,k2,k3;  // 反復変数
  int f;  // 条件変数
  
  k1 = 0;  // 反復変数の初期化
  
  while( 1 ) {  // -1が出るまで入力
    scanf("%d",&t);
    if( t == -1 ) break;
    array[k1] = t;
    k1++;
  }
  
  for( k2=0; k2<k1; k2++ ){
    min = array[k2];  // 最小値の初期化
    f = 0;  // 条件の初期化
    for( k3=k2; k3<k1; k3++ ){
      if( min > array[k3] ) {
        min = array[k3];
        min_pos = k3;
        f = 1;
      }
    }
    if( f ){  // 後ろの配列に最小値が存在する場合前に持ってくる
      t = array[k2];
      array[k2] = min;
      array[min_pos] = t;
    }
  }
  
  for( k2=0; k2<k1; k2++ ){ // 列挙
    printf("%d ",array[k2]);
  }
  
  return 0;
}

先輩からバブルソートという単語を聞いたが知らないので適当に組んでみた。
これは選択ソートと呼ばれるソートでバブルソートより早く挿入ソートより遅いソートらしい。

とりあえず時間があればバブルソートや挿入ソートで組み直してみたいと思う。

P.S. コードを表示するためはてな記法モードで書いたがHTMLがよくわからないので書きづらい。
HTMLも勉強したほうがいいだろうか。

ブログ作ってみました

某おじさんに脅されて書くといいよと言われてブログを作ってみました。

2015年10月8日現在の環境は

OS:WINDOWS10Pro

CPU:Intel Corei7-4700MQ 2.40Ghz

メモリ:8GB

エディタ:サクラエディタ

C言語のコンパイラ:gcc4.8.1

です。

2015年10月1日にWindows8.1ProからWindows10Proにアップグレードしました。