EeePC901

以前から買う買うと言ってたEeePCをやっと入手ッ!

この軽さッ!小ささッ!

f:id:yasutomo57jp:20080824224222j:image

カスタマイズしまくって使い倒します.

InsertionSort(挿入ソート:基本挿入法)(Ruby編)

InsertionSort(挿入ソート:基本挿入法)のRubyによる実装

def insertionsort(array)
ret = []
array.each do | val |
inspoint = ret.size
ret.each_with_index do | rval, index |
if val < rval
inspoint=index
break
end
end
ret.insert(inspoint,val)
end
return ret
end

うまく書けなかった・・・.

InsertionSort(挿入ソート:基本挿入法)(C言語編)

InsertionSort(挿入ソート:基本挿入法)のC言語による実装

#include "insertion.h"
void insertionsort(int *array,int size){
int i,j,k;
int temp;
// 挿入対象ごとに繰り返し
for(i=0;i<size;i++){
// 挿入位置を探索
for(j=0;j<i;j++)
if(array[i] < array[j]) break;
// 入れ替え
temp=array[i];
for(k=i;j<k;k--)array[k]=array[k-1];
array[j]=temp;
}
}

配列を使って実現しているので,非常に効率が悪い.

リストを使うと,後半の「入れ替え」部分の計算量がO(1)になる.

InsertionSort(挿入ソート:基本挿入法)

ソート済みの列に対し,未整列データをひとつずつ挿入していく.

配列は挿入が苦手なため,リスト構造などを用いて実現することが多い.

5 4 3 6 2が入力された場合,先頭の5がソート済み列であるとして,

4 5 3 6 2 # 4を5の前へ挿入,4 5 がソート済み列
3 4 5 6 2 # 3を4の前へ挿入,3 4 5 がソート済み列
3 4 5 6 2 # 6を5の後ろへ挿入,3 4 5 6 がソート済み列
2 3 4 5 6 # 2を3の前へ挿入,2 3 4 5 6 がソート済み列

となる.

BubbleSort(バブルソート:基本交換法)(C言語編)

BubbleSort(バブルソート:基本交換法)のC言語による実装.

/**
 * @file bubble.c
 * @author yasutomo57jp
 * */
#include "mylib.h"
/** 
 * @brief バブルソート
 * 
 * @param array ソート対象の配列
 * @param size 配列の大きさ
 */
void bubblesort(int *array, int size){
int i,j;
for(i=0;i<size-1;i++)
for(j=0;j<size-1-i;j++)
if(array[j]>array[j+1])swap(array+j,array+j+1);
}

これに伴い,mylib.hに次を追加.

void swap(int *i,int *j);

さらに,mylib.cに次を追加.

/** 
 * @brief 変数の内容を交換する
 * 
 * @param i 入力値1
 * @param j 入力値2
 */
void swap(int *i,int *j){
int temp=*i;
*i=*j;
*j=temp;
}