バブルソートは諦めて選択ソート

このエントリーをはてなブックマークに追加
はてなブックマーク - バブルソートは諦めて選択ソート
Facebook にシェア
[`google_buzz` not found]
[`yahoo` not found]
[`livedoor` not found]
[`friendfeed` not found]

さっきのやつを修正した.今回はちゃんと動いているぽい.

#!/usr/bin/env gosh
(define (selectsort listdata)
(define (exceptmax lst)
(if (pair? lst)
(if (= (fold max -1 lst) (car lst))
(cdr lst)
(append (list (car lst)) (exceptmax (cdr lst)))
)
()
)
)
(if (pair? listdata)
(append (selectsort (exceptmax listdata)) (list (fold max -1 listdata)))
listdata
)
)
(define (main args)
(let ((inputlist `(9 0 1 8 2 7 3 6 4 5)))
(print inputlist)
(print (selectsort inputlist))
)
)

Gauche3日目にして

このエントリーをはてなブックマークに追加
はてなブックマーク - Gauche3日目にして
Facebook にシェア
[`google_buzz` not found]
[`yahoo` not found]
[`livedoor` not found]
[`friendfeed` not found]

さっきまでのプログラムをよく見たら(別データで試したら)全然ソーティングできてなかった(恥

というかめちゃくちゃだった.

直します….

Gauche3日目

このエントリーをはてなブックマークに追加
はてなブックマーク - Gauche3日目
Facebook にシェア
[`google_buzz` not found]
[`yahoo` not found]
[`livedoor` not found]
[`friendfeed` not found]

注:このプログラムは間違えています.

昨日のBubbleSortをもうちょっと修正.

letを使って複数出てくる(bsort-swap (car lstdata) (cdr lstdata))をまとめた.

#!/usr/bin/env gosh
(define (bsort lstdata)
(define (bsort-swap x lst)
(if (pair? lst)
(if (< x (car lst))
(append (list x) lst)
(append (list (car lst)) (bsort-swap x (cdr lst)))
)
(list x)
)
)
(if (pair? lstdata)
(let (( sortlist (bsort-swap (car lstdata) (cdr lstdata))))
(append (list (car sortlist)) (bsort (cdr sortlist)))
)
lstdata
)
)
(define (main args)
(let ((inputlist `(9 0 1 8 2 7 3 6 4 5)))
(print inputlist)
(print (bsort inputlist))
)
)

またちょっとすっきりした.

さらにGauche2日目

このエントリーをはてなブックマークに追加
はてなブックマーク - さらにGauche2日目
Facebook にシェア
[`google_buzz` not found]
[`yahoo` not found]
[`livedoor` not found]
[`friendfeed` not found]

defineの中でさらにdefineできるらしい.ある関数Aからしか呼ばれないようなローカルな関数(?)Bを作る場合は,関数Aの定義内でBを定義する方が良い.

そこで,バブルソートを修正.

注:このプログラムは間違えています.

#!/usr/bin/env gosh
(define (bsort lstdata)
(define (bsort-swap x lst)
(if (pair? lst)
(if (< x (car lst))
(append (list x) lst)
(append (list (car lst)) (bsort-swap x (cdr lst)))
)
(list x)
)
)
(if (pair? lstdata)
(
append (list (car (bsort-swap (car lstdata) (cdr lstdata))))
(bsort (cdr (bsort-swap (car lstdata) (cdr lstdata))))
)
lstdata
)
)
(define (main args)
(let ((inputlist `(9 0 1 8 2 7 3 6 4 5)))
(print inputlist)
(print (bsort inputlist))
)
)

すっきりしたかな….(ソーティングがこれでいいのかは未だ疑問)

Gaucheでバブルソート

このエントリーをはてなブックマークに追加
はてなブックマーク - Gaucheでバブルソート
Facebook にシェア
[`google_buzz` not found]
[`yahoo` not found]
[`livedoor` not found]
[`friendfeed` not found]

FizzBuzzしたし,とりあえずソーティングでもやってみるか~と思ってバブルソートしてみた.

ら,鬼のようにむずかった(涙

Gauche1日目にして無茶した.

注:このプログラムは間違えています.

#!/usr/bin/env gosh
(define bsort-swap
(lambda (x lst)
(if (pair? lst)
(if (< x (car lst))
(append (list x) lst)
(append (list (car lst)) (bsort-swap x (cdr lst)))
)
(list x)
)
)
)
(define bsort
(lambda (lstdata)
(if (pair? lstdata)
(append
(list (car (bsort-swap (car lstdata) (cdr lstdata))))
(bsort (cdr (bsort-swap (car lstdata) (cdr lstdata))))
)
lstdata
)
)
)
(define (main args)
(let ((inputlist `(9 0 1 8 2 7 3 6 4 5)))
(print inputlist)
(print (bsort inputlist))
)
)

こんなんでいいのかな?もっとうまく書けそうな気もするが.まあいいか.初日だし.

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

このエントリーをはてなブックマークに追加
はてなブックマーク - InsertionSort(挿入ソート:基本挿入法)(Ruby編)
Facebook にシェア
[`google_buzz` not found]
[`yahoo` not found]
[`livedoor` not found]
[`friendfeed` not found]

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言語編)
Facebook にシェア
[`google_buzz` not found]
[`yahoo` not found]
[`livedoor` not found]
[`friendfeed` not found]

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(挿入ソート:基本挿入法)

このエントリーをはてなブックマークに追加
はてなブックマーク - InsertionSort(挿入ソート:基本挿入法)
Facebook にシェア
[`google_buzz` not found]
[`yahoo` not found]
[`livedoor` not found]
[`friendfeed` not found]

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

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

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言語編)
Facebook にシェア
[`google_buzz` not found]
[`yahoo` not found]
[`livedoor` not found]
[`friendfeed` not found]

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