明解 Javaによるアルゴリズムとデータ構造 6-3_単純選択ソート
6-3 単純選択ソート straight selection sort
最小要素を先頭に、2番めに小さい要素を先頭から2番目に移動する、を繰り返すアルゴリズム
- 未ソート部から最小のキーを持つ a[min] を選択
- a[min] と、未ソート部の先頭要素を交換
- 離れた要素を交換する可能性があるため、安定ではない
- 比較回数 :
- 1パスにつき、最小要素1つに、その他の要素を n - (現パス数) 回ぶつけて最小判定。それを n - 1 パス実施
ソースコード(途中経過表示板)
import java.util.Scanner;
class SelectionSort {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void selectionSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
System.out.println("パス: " + (i + 1));
int min = i;
for (int j = i + 1; j < n; j++) { // j -> 交換検討対象のインデックス
if (a[j] < a[min]) {
// ソート前状態の表示
for (int k = 0; k < n; k++) {
if (k == min) {
System.out.printf("%2d* ", a[k]); // "*" -> 現時点での最小要素
} else if (k == j) {
System.out.printf("%2d+ ", a[k]); // "+" -> 比較の結果新たに最小となった要素
} else {
System.out.printf("%2d ", a[k]);
}
}
System.out.println();
min = j;
} else {
// ソート前状態の表示
for (int k = 0; k < n; k++) {
if (k == min) {
System.out.printf("%2d* ", a[k]);
} else if (k == j) {
System.out.printf("%2d- ", a[k]); // "-" -> 比較の結果最小にならなかった要素
} else {
System.out.printf("%2d ", a[k]);
}
}
System.out.println();
}
}
swap(a, i, min);
// ソート後状態の表示
for (int e : a) {
System.out.printf("%2d ", e);
}
System.out.println();
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("単純選択ソート");
System.out.print("要素数: ");
int nx = stdIn.nextInt();
;
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "]:");
x[i] = stdIn.nextInt();
}
selectionSort(x, nx);
System.out.println("昇順にソートしました");
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}
単純選択ソート 要素数: 4 x[0]: 4 x[1]: 3 x[2]: 2 x[3]: 1 パス: 1 4* 3+ 2 1 4 3* 2+ 1 4 3 2* 1+ 1 3 2 4 パス: 2 1 3* 2+ 4 1 3 2* 4- 1 2 3 4 パス: 3 1 2 3* 4- 1 2 3 4 昇順にソートしました x[0] = 1 x[1] = 2 x[2] = 3 x[3] = 4
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る
明解 Javaによるアルゴリズムとデータ構造 6-2_バブルソート
6-2 バブルソート
概要
隣り合う2要素の大小関係を調べて必要に応じて交換を繰り返す、単純交換ソート straight exchange sort の一種。
- 要素数 n の配列に対して、n-1 回の比較・交換(この作業をパスという)を行うことで、最小要素を先頭に移動する
- 更に n-2 回の比較・交換で、2倍目に小さい要素をソートできる
- …(以下同様)
- パスを k 回行えば、先頭側 k 個の要素がソート済みとなる
液体中の気泡がぶくぶくと上に上がってくるイメージ → バブルソート！
- 隣り合う2つを交換するだけのため、安定なアルゴリズムである点に留意
計算量
合計比較回数:
合計交換回数の平均:
- (比較の半分が交換を伴うとして、) 合計比較回数 / 2 =
合計移動回数の平均:
- (swap()内で代入が3回行われるので、) 合計交換回数の平均 * 3 =
ソースコード（初版）
- ケツからソート版
import java.util.Scanner;
class BubbleSort {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = n - 1; j > i; j--) {
if (a[j - 1] > a[i]) {
swap(a, j - 1, j);
}
}
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("単純交換ソート(バブルソート)");
System.out.print("要素数: ");
int nx = stdIn.nextInt();
;
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "]:");
x[i] = stdIn.nextInt();
}
bubbleSort(x, nx);
System.out.println("昇順にソートしました");
for (int i = 0; i < nx; i++) {
System.out.println("x[ " + i + "] = " + x[i]);
}
}
}
- 頭からソート版
import java.util.Scanner;
class BubbleSortFromTop {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("単純交換ソート(バブルソート)");
System.out.print("要素数: ");
int nx = stdIn.nextInt();
;
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "]:");
x[i] = stdIn.nextInt();
}
bubbleSort(x, nx);
System.out.println("昇順にソートしました");
for (int i = 0; i < nx; i++) {
System.out.println("x[ " + i + "] = " + x[i]);
}
}
}
- 頭からソートして、途中経過を標準出力する版
import java.util.Scanner;
class BubbleSortFromTop {
static int comparisonCnt = 0;
static int changeCnt = 0;
static int moveCnt = 0;
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
moveCnt += 3;
}
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
System.out.println("パス" + i + ": ");
//ソート途中経過
for (int j = 0; j < n - 1 - i; j++) {
// 比較対象でない場合はただ標準出力するだけ
for (int k = 0; k < j; k++) {
System.out.printf("%2d ", a[k]);
}
// 比較対象であり、かつ交換される場合
if (a[j] > a[j + 1]) {
System.out.printf("%2d +%2d ", a[j], a[j + 1]);
swap(a, j, j + 1);
for (int k = j + 2; k < n; k++) {
System.out.printf("%2d ", a[k]);
}
System.out.print("\n");
changeCnt++;
// 比較対象であり、かつ交換されない場合
} else {
System.out.printf("%2d -%2d ", a[j], a[j + 1]);
for (int k = j + 2; k < n; k++) {
System.out.printf("%2d ", a[k]);
}
System.out.print("\n");
}
comparisonCnt++;
}
//交換後の一覧表示
StringBuilder sb = new StringBuilder();
for (int k = 1; k <= n; k++) {
sb.append("----");
}
System.out.println(sb.toString());
for (int e : a) {
System.out.printf("%2d ", e);
}
System.out.print("\n\n");
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("単純交換ソート(バブルソート)");
System.out.print("要素数: ");
int nx = stdIn.nextInt();
;
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "]:");
x[i] = stdIn.nextInt();
}
bubbleSort(x, nx);
System.out.println("昇順にソートしました");
for (int i = 0; i < nx; i++) {
System.out.println("x[ " + i + "] = " + x[i]);
}
System.out.println();
System.out.println("比較は " + comparisonCnt + " 回でした。");
System.out.println("移動は " + moveCnt + " 回でした。");
System.out.println("交換は " + changeCnt + " 回でした。");
}
}
-
- 出力結果はこんな感じ
単純交換ソート(バブルソート) 要素数: 5 x[0]: 1 x[1]: 2 x[2]: 3 x[3]: 6 x[4]: 5 パス0: 1 - 2 3 6 5 1 2 - 3 6 5 1 2 3 - 6 5 1 2 3 6 + 5 -------------------- 1 2 3 5 6 パス1: 1 - 2 3 5 6 1 2 - 3 5 6 1 2 3 - 5 6 -------------------- 1 2 3 5 6 パス2: 1 - 2 3 5 6 1 2 - 3 5 6 -------------------- 1 2 3 5 6 パス3: 1 - 2 3 5 6 -------------------- 1 2 3 5 6 昇順にソートしました x[ 0] = 1 x[ 1] = 2 x[ 2] = 3 x[ 3] = 5 x[ 4] = 6 比較は 10 回でした。 移動は 3 回でした。 交換は 1 回でした。
ソースコード（第2版）
打ち切りを導入
あるパス内で、一度も交換が行われない ⇒ ソートは完了している- パス内での交換回数を記録するローカル変数を追加
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
int exchg = 0;
for (int j = n - 1; j > i; j--) {
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
exchg++;
}
}
if (exchg == 0) {
break;
}
}
}
- 途中経過表示版
import java.util.Scanner;
class BubbleSort2 {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void bubbleSort(int[] a, int n) {
// パスのループ
for (int i = 0; i < n - 1; i++) {
int exchg = 0;
System.out.println("パス : " + i);
// パス内での、隣接要素比較のループ
for (int j = n - 1; j > i; j--) {
// 比較対象要素の直前までを標準出力
for (int k = 0; k < j - 1; k++) {
System.out.printf("%2d ", a[k]);
}
if (a[j - 1] > a[j]) {
System.out.printf("%2d +%2d ", a[j-1], a[j]); // 交換前の比較対象要素を出力
for (int k = j + 1; k < n; k++) {
System.out.printf("%2d ", a[k]);
}
System.out.println();
swap(a, j - 1, j);
exchg++;
} else {
System.out.printf("%2d -%2d ", a[j-1], a[j]); // 交換前の比較対象要素を出力
for (int k = j + 1; k < n; k++) {
System.out.printf("%2d ", a[k]);
}
System.out.println();
}
}
if (exchg == 0) {
break;
}
for (int e : a) {
System.out.printf("%2d ", e); // パス完了時の並びを出力
}
System.out.print("\n\n");
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("単純交換ソート(バブルソート)");
System.out.print("要素数: ");
int nx = stdIn.nextInt();
;
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "]:");
x[i] = stdIn.nextInt();
}
bubbleSort(x, nx);
System.out.println("昇順にソートしました");
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}
単純交換ソート(バブルソート) 要素数: 5 x[0]: 9 x[1]: 1 x[2]: 5 x[3]: 8 x[4]: 4 パス : 0 9 1 5 8 + 4 9 1 5 + 4 8 9 1 - 4 5 8 9 + 1 4 5 8 1 9 4 5 8 パス : 1 1 9 4 5 - 8 1 9 4 - 5 8 1 9 + 4 5 8 1 4 9 5 8 パス : 2 1 4 9 5 - 8 1 4 9 + 5 8 1 4 5 9 8 パス : 3 1 4 5 9 + 8 1 4 5 8 9 昇順にソートしました x[0] = 1 x[1] = 4 x[2] = 5 x[3] = 8 x[4] = 9
ソースコード（第3版）
前パスで既にソート済みの要素比較をスキップ
static void bubbleSort(int[] a, int n) {
int k = 0; // ソート済インデックスのマーカー(パスをまたぐ変数)
while (k < n - 1) {
int last = n - 1; // 前パスで最後に交換したインデックス
for (int j = n - 1; j > k; j--) {
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
last = j;
}
}
k = last;
}
}
疑問
- line8 と line11 でそれぞれ代入する意味ってなんだ？
- k に逐次 j 突っ込むんじゃダメだっけ？
static void bubbleSort(int[] a, int n) {
int k = 0; // ソート済インデックスのマーカー(パスをまたぐ変数)
while (k < n - 1) {
for (int j = n - 1; j > k; j--) {
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
k = j;
}
}
}
}
回答
- 挙動正しく理解できてなかった。
- for 内で k = j 突っ込んじゃうと、swap対象な j の場合、forから即出ちゃうね・・・
- k は漸減していくパラメータであり、1パス完走した時の最小値が意味を持つ。
- よって、for ループに関係しない変数で j を確保しといて、for ループ回りきった後に、その最小値を k に代入する仕組みが必要。
途中経過表示版
import java.util.Scanner;
class BubbleSort3 {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void bubbleSort(int[] a, int n) {
int k = 0; // ソート済インデックスのマーカー(パスをまたぐ変数)
while (k < n - 1) {
System.out.println("パス: " + (k+1));
int last = n - 1; // 最後に交換したインデックス
for (int j = n - 1; j > k; j--) {
// 比較対象以前の要素を表示
for (int l = 0; l < j - 1; l++) {
System.out.printf("%2d ", a[l]);
}
// 比較
if (a[j - 1] > a[j]) {
// 交換対象箇所を表示
System.out.printf("%2d +%2d ", a[j-1], a[j]);
swap(a, j - 1, j);
last = j;
} else {
// 非交換対象箇所を表示
System.out.printf("%2d -%2d ", a[j-1], a[j]);
}
// 比較対象箇所以降の要素を表示
for (int l = j + 1; l < n; l++) {
System.out.printf("%2d ", a[l]);
}
System.out.println();
}
for (int e : a) {
System.out.printf("%2d ", e);
}
System.out.println();
k = last;
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("単純交換ソート(バブルソート)");
System.out.print("要素数: ");
int nx = stdIn.nextInt();
;
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "]:");
x[i] = stdIn.nextInt();
}
bubbleSort(x, nx);
System.out.println("昇順にソートしました");
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}
単純交換ソート(バブルソート) 要素数: 5 x[0]: 1 x[1]: 2 x[2]: 3 x[3]: 5 x[4]: 4 パス: 1 1 2 3 5 + 4 1 2 3 - 4 5 1 2 - 3 4 5 1 - 2 3 4 5 1 2 3 4 5 昇順にソートしました x[0] = 1 x[1] = 2 x[2] = 3 x[3] = 4 x[4] = 5
双方向バブルソート bidirection bubble sort / シェーカーソート shaker sort
- 『最小要素を先頭側に』と『最大要素を末尾側に』を組み合わせたソート法
- ほぼほぼソートされているが、大きめの値がぽつんと先頭付近にあったりする際(あるいはその逆)の場合有効
ソースコード
- shakerSort()がデブっててかっこ悪いので、あれな感じだな
import java.util.Scanner;
class ShakerSort {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void shakerSort(int[] a, int n) {
int k = 0; // ソート済インデックスのマーカー
int l = n - 1; // ソート済インデックスのマーカー
int pathNo = 1; // 現在のパス数
boolean topSorted = false; // トップソートの完了フラグ
boolean bottomSorted = false; // ボトムソートの完了フラグ
while (!topSorted && !bottomSorted) {
System.out.println("パス: " + pathNo);
// 奇数パス -> 最小値を先頭へ
if (pathNo % 2 == 1) {
int last = n - 1; // 最後に交換したインデックス
for (int j = n - 1; j > k; j--) {
// 比較対象以前の要素を表示
for (int m = 0; m < j - 1; m++) {
System.out.printf("%2d ", a[m]);
}
// 比較
if (a[j - 1] > a[j]) {
// 交換対象箇所を表示
System.out.printf("%2d +%2d ", a[j - 1], a[j]);
swap(a, j - 1, j);
last = j;
} else {
// 非交換対象箇所を表示
System.out.printf("%2d -%2d ", a[j - 1], a[j]);
}
// 比較対象箇所以降の要素を表示
for (int m = j + 1; m < n; m++) {
System.out.printf("%2d ", a[m]);
}
System.out.println();
}
k = last;
// 偶数パス -> 最大値を末尾へ
} else {
int last = 0; // 最後に交換したインデックス
for (int j = 0; j < n - k; j++) {
// 比較対象以前の要素を表示
for (int m = 0; m < j; m++) {
System.out.printf("%2d ", a[m]);
}
// 比較
if (a[j] > a[j + 1]) {
// 交換対象箇所を表示
System.out.printf("%2d +%2d ", a[j], a[j + 1]);
swap(a, j, j + 1);
last = j;
} else {
// 非交換対象箇所を表示
System.out.printf("%2d -%2d ", a[j], a[j + 1]);
}
// 比較対象箇所以降の要素を表示
for (int m = j + 2; m < n; m++) {
System.out.printf("%2d ", a[m]);
}
System.out.println();
}
l = last;
}
// 各パスでのソート結果表示
for (int e : a) {
System.out.printf("%2d ", e);
}
System.out.println();
// ボトムソート・トップソート完了判定
if (k >= n - 1)
topSorted = true;
if (l <= 1) {
bottomSorted = true;
}
pathNo++;
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("単純交換ソート(バブルソート)");
System.out.print("要素数: ");
int nx = stdIn.nextInt();
;
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "]:");
x[i] = stdIn.nextInt();
}
shakerSort(x, nx);
System.out.println("昇順にソートしました");
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}
参考) 第三版とシェーカーソートとの差分
- 第三版
単純交換ソート(バブルソート) 要素数: 7 x[0]: 9 x[1]: 1 x[2]: 3 x[3]: 4 x[4]: 6 x[5]: 7 x[6]: 8 パス: 1 9 1 3 4 6 7 - 8 9 1 3 4 6 - 7 8 9 1 3 4 - 6 7 8 9 1 3 - 4 6 7 8 9 1 - 3 4 6 7 8 9 + 1 3 4 6 7 8 1 9 3 4 6 7 8 パス: 2 1 9 3 4 6 7 - 8 1 9 3 4 6 - 7 8 1 9 3 4 - 6 7 8 1 9 3 - 4 6 7 8 1 9 + 3 4 6 7 8 1 3 9 4 6 7 8 パス: 3 1 3 9 4 6 7 - 8 1 3 9 4 6 - 7 8 1 3 9 4 - 6 7 8 1 3 9 + 4 6 7 8 1 3 4 9 6 7 8 パス: 4 1 3 4 9 6 7 - 8 1 3 4 9 6 - 7 8 1 3 4 9 + 6 7 8 1 3 4 6 9 7 8 パス: 5 1 3 4 6 9 7 - 8 1 3 4 6 9 + 7 8 1 3 4 6 7 9 8 パス: 6 1 3 4 6 7 9 + 8 1 3 4 6 7 8 9 昇順にソートしました x[0] = 1 x[1] = 3 x[2] = 4 x[3] = 6 x[4] = 7 x[5] = 8 x[6] = 9
- シェイカー
単純交換ソート(バブルソート) 要素数: 7 x[0]: 9 x[1]: 1 x[2]: 3 x[3]: 4 x[4]: 6 x[5]: 7 x[6]: 8 パス: 1 9 1 3 4 6 7 - 8 9 1 3 4 6 - 7 8 9 1 3 4 - 6 7 8 9 1 3 - 4 6 7 8 9 1 - 3 4 6 7 8 9 + 1 3 4 6 7 8 1 9 3 4 6 7 8 パス: 2 1 - 9 3 4 6 7 8 1 9 + 3 4 6 7 8 1 3 9 + 4 6 7 8 1 3 4 9 + 6 7 8 1 3 4 6 9 + 7 8 1 3 4 6 7 9 + 8 1 3 4 6 7 8 9 パス: 3 1 3 4 6 7 8 - 9 1 3 4 6 7 - 8 9 1 3 4 6 - 7 8 9 1 3 4 - 6 7 8 9 1 3 - 4 6 7 8 9 1 3 4 6 7 8 9 パス: 4 1 - 3 4 6 7 8 9 1 3 4 6 7 8 9 昇順にソートしました x[0] = 1 x[1] = 3 x[2] = 4 x[3] = 6 x[4] = 7 x[5] = 8 x[6] = 9
- 解答抜粋 - BohYoh.com【著書】明解Javaによるアルゴリズムとデータ構造《演習問題6-5の解答》
- こっちのほうが終了条件スマートでいいな
//--- 双方向バブルソート（シェーカーソート）---//
static void shakerSort(int[] a, int n) {
int left = 0;
int right = n - 1;
int last = right;
while (left < right){
for (int j = right; j > left; j--){
if (a[j - 1] > a[j]){
swap(a, j - 1, j);
last = j;
}
}
left = last;
for (int j = left; j < right; j++){
if (a[j] > a[j + 1]){
swap(a, j, j + 1);
last = j;
}
}
right = last;
}
}
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る
明解 Javaによるアルゴリズムとデータ構造 6-1_ソートとは
6-1 ソートとは
安定性
- 安定 stable
- 同一キーを持つ要素の順序関係が、ソート前後で必ず維持される
- 不安定
- 同一キーを持つ要素の順序関係が、ソート前後で維持されるとは限らない
ソートの考え方
- ソートアルゴリズムの3大要素
- 交換
- 選択
- 挿入
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る
空気清浄機を買った (ダイキン: ACK55N-W)
空気清浄機購入に至る流れと、ネット通販で、ふと思ったこと。
なんで買ったの？
- 空気中のホコリが多い気がする
- 部屋が狭い。一方で寝具の容積は一般的なもの。
- 結果、部屋の容積に対して、ホコリ発生源の体積比率が大きく、フローリングにすぐホコリが溜まる・・・
- 部屋が狭い。一方で寝具の容積は一般的なもの。
- 冬場に、空気がすごく乾燥して、気管支が辛い
要は、部屋の空気があまり快適ではなかったのです。
で、空気清浄機買うことにしました。
田舎じゃあ部屋広くてこんなん要らんかったから、初購入ですわー(ﾄﾞﾔ
メーカー選び
メーカーはダイキンにした。
エアコン何回か買ってるんだけど、他メーカーより明らかにクオリティ違った。
業者のおっちゃんの印象とも合致していて、空調関連機器はダイキン選んどけば安パイだよね～、って感じ。
3秒で決定。
機種選定
2012年9月モデルのこれになった。
ダイキン(DAIKIN) 加湿空気清浄機「うるおい光クリエール」 バニラホワイト ACK55N-W
- 出版社/メーカー: ダイキン
- メディア: ホーム&キッチン
- この商品を含むブログを見る
なんせ初で、機能も商品のリリースサイクルもよくわからんので、そのへんざっくり見た。
ダイキンは毎年9月にモデルチェンジがある模様。
んでもって、シングル世帯あるいはそれほど大きくない部屋向きと思われ、今回の購入候補となるMCK55/ACK55モデルにおいては、2012 -> 2013 のモデルチェンジはマイナーチェンジに相当し、大幅な機能追加は無し。
2012 モデルと 2013 モデルの価格差は \10,000 程度。
デザインも変わらんし、じゃあ2012年モデルでいいやー、っと決定。
高々2万ぐらいの商品なんで、長々時間かけても得する額が大きいわけでもない。
30分でエイヤッと決定。
店選び
店頭はめんどいのでナシ。
いちいち出向いて値切りとか、タルいっす。
少なくとも要した時間分は、値引きして返してほしいよね、とか思うけど、たいていそんなとこまで下がんないのでネット通販です。
ヒッキーだからじゃないんだからねっ！
購入した通販サイトは、YAHOO!ショッピングの小規模通販サイト。楽天 - 23,400円 にも YAHOO!ショッピング - 21,863円 にも系列店持ってるようだが、YAHOO!ショッピングのほうが、楽天よりちょっと安いね。
2,000円弱。
手数料として楽天により多く納めてる分を、価格転嫁してるんかな。
楽天最弱説
楽天でほしいもんあった場合、最安ではない可能性が高いから、amazon と YAHOO!ショッピングでも検索かけると幸せになれるね。
あとは、クレカのWEBサイト経由で買いもんすることで、ちょっとポイントもらえるぐらいかな。
まあ今回のケースだとクレカWEBサイト経由で得するのは500円弱だったので、マクド一回分に満たないぐらい。
面倒さとペイするかは微妙。
つーか、amazonには品揃えで負けるし、値段ではYAHOO!に負けるし、楽天のほうが勝つ領域って何かなー。
出店してる業者も情弱色が強い。
amazonのマケプレとかの勝手にやってくれ感に較べて、縦長で糞うざい楽天テンプレだったり、なんやかんやでネット進出のハードル下げることについては一番親切なのかな。
手数料ガッチリとって、厚いサポート体制を用意して、その結果、最も恩恵を蒙る登場人物が、出店者でも消費者でなく、おそらく楽天であるあたりが非常に日本的だなあと思ったり。
日本的というか、前時代的というべきなのかな。
だからダメとは言わないが、尻窄んでいく気がするな。
所感
今週ぐらいに届くだろうから、後で記録するぜー。
(2013/01/11追記)
いらっしゃいました。
とりあえず初回稼働。
意外と風つえー。
コーって言ってる。
動作面では特に問題なさそうー。
ハウスダストの量を、インジケータ表示してくれるから、掃除サボれなくなるのがいいね！
湿度インジケータ見たら、だいぶ乾燥してる。
全力で加湿してもすぐには上がってこないあたり、相当やな。
冬の間は全力加湿でいこうと思うのねん。
気管支やられる割合を下げたい。
体調管理はホント大事。
明解 Javaによるアルゴリズムとデータ構造 5_再帰的アルゴリズム
5-1 再帰の基本
メソッド内で自分を呼びだす
- 階乗
- ユークリッドの互除法
- ハノイの塔
5-2 再帰アルゴリズムの解析
- 解析
- トップダウン
- ボトムダウン
- 真に再帰的
- メソッド内で自身を複数回呼び出すもの
- 挙動が複雑
- 非再帰への書き換え
- 末尾再帰は容易 - http://d.hatena.ne.jp/yaneurao/20051008
- スタックを用いて過着換えることが出来る場合もあるが、一般に可能とは言い切れない
5-3 ハノイの塔
非再帰への書き下し解答があんまりしっくりこないので、あとで振り返る
5-4 8王妃問題
8x8チェス盤上に、互いに取れないように合計8クイーンを配置する問題
クイーンは縦横斜めに移動できる(飛車と角の動きを併せ持つ感じ)
列ごとに1王妃配置する場合の全配置パターン書き下しアルゴ。
なんてことない再帰なんだけど、すぐには挙動読み取れんかった。
- 分岐 branching
- 分割統治法 devide and conquer
class QueenB {
static int[] pos = new int[8];
static void print() {
for (int i = 0; i < 8; i++) {
System.out.printf("%2d", pos[i]);
}
System.out.println();
}
/**
* 女王のいる行数: j=0 からスタート
*
* 女王j=0 で固定したまま列数をインクリメントして、潜る。
* 列i=7 まで来たら、結果を出力
* 列i=7 のまま 女王j++ -> j=7 まできたら、列i=7のセットは終わり。i=6にpopしてくる。
*
* 列i=6における、j=0が完了し、j++ -> j=7 まできたら、列i=6のセットは終わり。i=5にpopしてくる。
* 列i=5における、j=0が完了し、j++ -> j=7 まできたら、列i=5のセットは終わり。i=4にpopしてくる。
* ：
* ：
* ：
* 列i=1における、j=0が完了し、j++ -> j=7 まできたら、列i=1のセットは終わり。done!
*
* @param i 王妃配置対象の列
*/
static void set(int i) { // i は
for (int j = 0; j < 8; j++) { // j は女王を配置する行数
pos[i] = j;
if (i == 7) {
print();
} else {
set(i+1); // 考慮する対象列をインクリメント
}
}
}
public static void main(String[] args) {
set(0);
}
}
以下、挙動のメモ。
i=0 j=0から始まる 1 0 2 0 3 0 4 0 // set(5) 5 0 // set(6) 6 0 // set(7) 7 0 print 7 1 print 7 2 print 7 3 print 7 4 print 7 5 print 7 6 print 7 7 print 6 1 // set(7) 7 0 print 7 1 print 7 2 print 7 3 print 7 4 print 7 5 print 7 6 print 7 7 print 6 2 // set(7) 7 0 print 7 1 print 7 2 print 7 3 print 7 4 print 7 5 print 7 6 print 7 7 print 6 3 6 4 6 5 6 6 6 7 5 1 ： ： ：8王妃問題のソルバー(解を盤面表示する)。 なお、このソルバーは
- 限定 bounding
- 分枝限定法 branching and bounding method
class EightQueen {
static boolean[] flag_a = new boolean[8];
static boolean[] flag_b = new boolean[15];
static boolean[] flag_c = new boolean[15];
static int[] pos = new int[8];
static void print() {
String[] board = new String[8];
for (int j = 0; j < 8; j++) { // j行
board[j] = "";
for (int i = 0; i < 8; i++) { // i列
board[j] += (pos[i] == j) ? "■" : "□";
}
System.out.println(board[j]);
}
System.out.println();
}
static void set(int i) {
for (int j = 0; j < 8; j++) {
if (flag_a[j] == false && flag_b[i + j] == false
&& flag_c[i - j + 7] == false) {
pos[i] = j;
if (i == 7) {
print();
} else {
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = true;
set(i + 1);
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = false;
}
}
}
}
public static void main(String[] args) {
set(0);
}
}
上記ソルバーを走らせると、以下の様な盤が92面出力される。■□□□□□□□ □□□□□□■□ □□□□■□□□ □□□□□□□■ □■□□□□□□ □□□■□□□□ □□□□□■□□ □□■□□□□□ ■□□□□□□□ □□□□□□■□ □□□■□□□□ □□□□□■□□ □□□□□□□■ □■□□□□□□ □□□□■□□□ □□■□□□□□ ■□□□□□□□ □□□□□■□□ □□□□□□□■ □□■□□□□□ □□□□□□■□ □□□■□□□□ □■□□□□□□ □□□□■□□□非再帰化、ちょっと考え中。
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る
明解 Javaによるアルゴリズムとデータ構造 4_スタックとキュー
4-1 スタック
フィールド: スタックの容量・ポインタ。後入れ先出し(LIFO - Last In First Out)。
- push, pop, peek, dump
- indexOf, size, clear, capacity
- isEmpty, isFull
4-2 キュー
フィールド: キューの容量・ポインタ。先入れ先出し(FIFO - First In First Out)。
- 配列キュー
- enqueue, dequeue, peek, dump
- indexOf, size, clear, capacity
- isEmpty, isFull
- リングバッファ(ring buffer)キュー
- 要素ピックアップ時の残要素シフトコストが、配列キューよりも下がるのがメリット
- max, front, rear, num
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る
