NON STOP TECH BLOG

ノンストップで書きまくる技術ブログ

Bubble sort(バブルソート)

C++ アルゴリズム JavaScript

相変わらずアルゴリズムの本を読んでいます〜
いつか役に立つと信じて...
今回はバブルソートです。

前提

バブルソートも前回の挿入ソートと同じく、ソート済み部分と未ソート部分に分けて考えます。

手順

  1. 配列の後ろから、隣り合う要素を順番に比較して、大小関係が逆ならば入れ替える。
    この操作を並びが正しくなるまで繰り返す。

ソースコード

本に乗ってるやつの変数名かえたり、コメントつけたやつです〜

#include<iostream>
using namespace std;

// バブルソート
int bubbleSort(int array[], int size) {
  // 並び替え回数カウント用
  int times = 0;
  bool flag = 1;
  // 順番が逆になっている要素がなくなるまで繰り返す
  // array[i]までがソート済み配列になる
  for ( int i = 0; flag; i++ ) {
    flag = 0;
    // 最後の要素から、未ソート部分すべての要素
    // を探索する
    for ( int j = size - 1; j >= i; j-- ) {
      // 順番が逆になっていたら入れ替える
      if ( array[j] < array[j-1]) {
        swap(array[j], array[j-1]);
        flag = 1;
        times++;
      }
    }
  }
  return times;
}

int main() {
  int array[100], size, times;

  cin >> size;

  for (int i=0; i<size; i++) cin >> array[i];

  times = bubbleSort(array, size);

  for (int i=0; i<size; i++){
    if (i) cout << " ";
    cout << array[i];
  }

  cout << endl;
  cout << times << endl;

  return 0;
}

JavaScript

JSでも書いてみました.
こっちは降順もあります

See the Pen Bubble sort by ysk (@00ysk) on CodePen.

Insertion Sort(挿入ソート)

C アルゴリズム JavaScript

寒い〜〜
クリスマスですね〜〜

最近、これを読み始めました。

https://www.amazon.co.jp/dp/4839952957/ref=cm_sw_em_r_mt_dp_U_qW0aEbEYV3WQF

メモ的に学んだことを残していきたいと思います。

前提

このアルゴリズムはソート対象の配列を、未ソート部分とソート済み部分にわけて考えます。
まだ並べ替えが行われていない段階では、先頭の要素がソート済みになります。

手順

未ソート部分がなくなるまで下の処理を繰り返します。

  1. 未ソート部分先頭から要素を一つ取り出して、変数に退避させます。(ここではこの変数をtmpとします)
  2. ソート済みの部分で、変数tmpより大きい要素を一つ後ろにずらします。
  3. ソート済みの部分で、空いたところに変数tmpを入れます。

ソースコード

本に乗ってるやつに自分なりに変数名つけたり、コメントつけたやつです。
コードを見てもらえば、わかると思うのですが、昇順のソートです。

#include<stdio.h>

// 配列の要素を順番に出力
void trace(int array[], int size)
{
  int i;
  for (i=0; i<size; i++)
  {
    // 最初は空白を入れないのでスキップ
    if (i>0) printf(" ");
    printf("%d", array[i]);
  }
  // 改行を出力
  printf("\n");
}

// 挿入ソート関数
void insertionSort(int array[], int size) {
  int prev, current, tmp;

  for (current = 1; current < size; current++)
  {
    // 未ソート部分の先頭要素を退避
    tmp = array[current];
    // prev(ソート済み部分列からtmpを挿入する位置を探すための変数)の値
    prev = current - 1;

    /**
     * 探索変数が配列の範囲内である　かつ
     * ソート済み部分の変数が退避した変数よりも大きい限り回す
     */
    while ( prev >= 0 && array[prev] > tmp)
    {
      // 一つ後ろに退避させる
      array[prev+1] = array[prev];
      // 探索対象を遡る
      prev--;
    }

    // 空いた場所に退避した未ソート部分の先頭を挿入
    array[prev+1] = tmp;

    // ログ
    trace(array, size);
  }
}

/**
* メイン
*/
int main()
{
  int size, current, prev;
  int array[100];

  scanf("%d", &size);
  for (current=0; current<size; current++)
  {
    scanf("%d", &array[current]);
  }

  trace(array, size);
  insertionSort(array, size);

  return 0;
}

本に乗ってる図がめちゃくちゃわかりやすいので、おすすめです。

JavaScript

普段はJSをメインで書いているのでJSでも書いてみました〜
こっちには降順のパターンも載せています。

See the Pen Insertion sort by ysk (@00ysk) on CodePen.

jestに入門してみた

プロジェクトにインストール。

yarn add —-dev jest

テストするfunctionを用意する。
sum.js

function sum(a, b) {
  return a + b;
}
module.exports = sum;

テストコードを書く。
sum.test.js

const sum = require('./sum');

test('1 + 2 = 3になること', () => {
  expect(sum(1, 2)).toBe(3);
});

package.jsonに test scriptを追加。

{
  “scripts”: {
    “Test”: “jest"
  }
}

テストを実行。

yarn test

グローバルに追加しておくことで、cliからjestを実行できる

yarn global add jest

2つほど質問されたあと、jest.config.jsが作成された

jest —init

jest.config.jsの中には

module.exports = {
...
  clearMocks: true,
...
  testEnvironment: "node",
};

とあった。質問の内容が反映されている。

プロジェクトでbabelを使う場合

yarn add —-dev babe-jest @babel/core @babel/preset-env

をインストール。

babel.config.jsを作成。

module.exports = {
  presets: [
    [
      '@babel/preset-env',
      {
        targets: {
        node: 'current',
        },
      },
    ],
  ],
};

TypeScriptを使う場合

yarn add —dev @babel/preset-typescript

babel.config.jsのpresetsに

presets: [
  ‘@babel/preset-typescript’,
]

を追記。

わからなかったこと

describe(name, fn)
  • これから name のテストをするよ、という宣言。ネストすることもできる

オブジェクト指向JavaScript

最近、あんまりアウトプットできてない...
反省...

オブジェクト指向JavaScriptについて勉強したのでメモです。
ほぼ↓に書いてあることをまとめただけの備忘録的なものです。

developer.mozilla.org

用語

⁃ ネームスペース
開発者があらゆる機能をアプリケーション固有の一意な名前にまとめることができる容器
⁃ 継承
あるクラスが別のクラスから特性を引き継ぐことを指します
⁃ カプセル化
データとそのデータを使用するメソッドをまとめる手法
⁃ 抽象化
実世界のモデルが、オブジェクトの複雑な継承、メソッド、プロパティの集合体によって適切に再現されている状態を指す
⁃ ポリモーフィズム
別々のクラスが同じメソッドやプロパティを定義可能で有ること

プロトタイプベースプログラミング

クラスを使わずにプロトタイプオブジェクトをデコレート（あるいは拡張）してそのオブジェクトの持つ挙動を再利用することで実現されるOOPモデル

JavaScriptのオブジェクト指向プログラミング

ネームスペース

ネームスペースはメソッド、プロパティ、オブジェクトを包含する別のオブジェクト
※ JavaScriptでは通常のオブジェクトとネームスペースとの間に、言語レベルの違いがない。

ネームスペースを作成するときは、グローバルオブジェクトを一つ作成して、すべての変数、メソッド、関数をそのオブジェクトのプロパティとすれば良い。

MYAPPが定義済みであれば、それを使用。なければ、空のオブジェクトを作成

var MYAPP = MYAPP || {};

サブネームスペースの作成

MYAPP.event = {};

変数、関数、メソッドを追加

// 共通のメソッドやプロパティ向けに MYAPP.commonMethod という名前のコンテナを作成
MYAPP.commonMethod = {
  regExForName: "", // 名前を検証するための正規表現を定義
  regExForPhone: "", // 電話番号を検証するための正規表現を定義
  validateName: function(name){
    // 名前に対してなんらかの処理を行う。"this.regExForName" を使用して
    // 変数 regExForName にアクセス可能
  },
 
  validatePhoneNo: function(phoneNo){
    // 電話番号に対してなんらかの処理を行う
  }
}

// オブジェクトとともにメソッドを定義する
MYAPP.event = {
    addListener: function(el, type, fn) {
    // 処理
    },
    removeListener: function(el, type, fn) {
    // 処理
    },
    getEvent: function(e) {
    // 処理
    }
    // 他のメソッドやプロパティを追加できる
}

// addListener メソッドを使用する構文:
MYAPP.event.addListener("yourel", "type", callback);

クラス

JavaScriptはクラスのコンストラクタとして関数を使用する。 Personクラスの作成

ver Person = function() {};

オブジェクト（クラスのインスタンス） Objオブジェクトの新たなインスタンスを生成するには new obj文を使用する。 Personコンストラクタから2つのインスタンスの生成

var person1 = new Person();
var person2 = new Person();

プロパティ（オブジェクトの属性）
プロパティは、クラス内にある変数。オブジェクトのインスタンスは全て、それらのプロパティを持つ。
プロパティはコンストラクタ内で設定される

Var Person = funtion (firstname) {
    This.firstName - firstName;
}

Person.prototype.sayHello = fuction() {
    console.log(“Hello, I’m ” + this.firstName);
};

var person1 = new Person(’bob’);
person1.sayHello();

var Person = function (firstName) {
  this.firstName = firstName;
};

Person.prototype.sayHello = function() {
  console.log("Hello, I'm " + this.firstName);
};

var person1 = new Person("Alice");
var person2 = new Person("Bob");
var helloFunction = person1.sayHello;

// "Hello, I'm Alice" と出力
person1.sayHello();

// "Hello, I'm Bob" と出力
person2.sayHello();

// "Hello, I'm undefined" と出力
// (strict モードでは TypeError で失敗する)
helloFunction();                                    

// true と出力
console.log(helloFunction === person1.sayHello);

// true と出力
console.log(helloFunction === Person.prototype.sayHello);

// "Hello, I'm Alice" と出力
helloFunction.call(person1);

sayHello関数を参照しているもの(person1, Person.prototype, helloFunctionなど)すべてが、同一の関数を示している。 thisの値は関数の呼び出し方に依存する。もっとも一般的な、オブジェクトのプロパティから関数にアクセスする形式（person1.sayHello())でthisをよびだすときは、その関数を持つオブジェクト(person1)をthisに設定する helloFunctionからthisを呼び出すと、グローバルオブジェクトをthisに設定する。

Function.callまたはFunction.applyを使用してThisを明示的に設定もできる。

継承

1つ以上のクラスを特化したバージョンとしてクラスを作成する方法。JavaScriptでは単一継承のみサポートしている。

var Person = function(firstName) {
    this.firstName = firstName;
};

Person.prototype.walk = function() {
    console.log(‘I am walking’);
}

Person.prototype.sayHello = function() {
    console.log(‘Hello, I’m’ + this.firstName);
}

// Studentコンストラクタの定義
Function Student(firstName, subject) {
    // 親のコンストラクタを呼び出す。呼び出しの際にThisが設定されるようにする
    Person.call(this.firstname);

    this.subject = subject;
};

// Person.prototypeを継承する、　Student.prototypeオブジェクトを作成
// Student.prototypeを生成するためにnew Personを使ってはならない
Student.prototype = Object.create(Person.prototype);

// constructorプロパティがStudentを指すように設定する
Student.prototype.constructor = Student;

Student.prototype.sayHello = function() {
    // …
}

Student.prototype.sayGoodBye = function() {
    // …
}

var student1 = new Student(‘janet’, ‘Math’);
student1.sayHello();
student1.walk();
student1.sayGoodBYe();

console.log(student1 instanceof Person); // true
console.log(student1 instanceof Student); // true

Function createObjcet(proto) {
    Function ctor() {}
    ctor.prototype = proto;
    Return new ctor();
}

オブジェクトをインスタンス化する方法を問わずに、thisの参照先を適切に指定するのはときに難しい。 これを用意にするシンプルなイディオム。

var Person = function(firstName) {
    If (this instanceof Person) {
        this.firstName = firstName;
    } else {
        Return new Person(fistName);
    }
}

抽象化

抽象化は、取り組んでいる問題の箇所を継承や合成によってモデル化することを可能にする仕組みです...?よくわからん

var foo = function () {};

// "foo is a Function: true" と出力
console.log('foo is a Function: ' + (foo instanceof Function));

// "foo.prototype is an Object: true" と出力
console.log('foo.prototype is an Object: ' + (foo.prototype instanceof Object));

ポリモーフィズム

すべてのメソッドやプロパティがprototypeプロパティの内部で実装されているのと同じように、異なるクラスで同じ名前のメソッドを定義できる。

Node.jsでルーティング

素のNode.jsでルーティングをするときのメモ

リクエストされたurlは

const url = req.url;

でとれる。

メソッドは

const method = req.method;

でとれる。

全体は下のような形になる

const http = require('http');

const server = http.createServer((req, res) => {
    const url = req.url;
    const method = req.method;

    // ルーティング
    if (url === '/') {
        // ...ルートにアクセスされたときの処理
    }

    if (url === '/hoge' && mehotd === 'POST') {
        // ..."/hoge"にPOSTされたときの処理
    }
});

Node.jsでPOSTされたデータをパースする

JavaScript Node.js 
const http = require('http');
const fs = require('fs');

const server = http.createServer((req, res) => {
  const url = req.url;
  const method = req.method;
  if (url === '/message' && method === 'POST') {
    const body = [];
    req.on('data', function (chunk) {
      body.push(chunk);
    });
    req.on('end', () => {
      const parseBody = Buffer.concat(body).toString();
      const message = parseBody.split('=')[1];
      fs.writeFileSync('message.txt', message);
    });
    res.statusCode = 302;
    res.setHeader('Location', '/');
    return res.end();
  }
});

server.listen(3000);

Node.jsでサーバーを立てる

簡単にメモ
素のnodeでやったことがなかったので

const http = require('http');

const server = http.createServer((req, res) => {
  console.log(req);
});

server.listen(3000);

htmlをレスポンスとして返す

const http = require('http');

const server = http.createServer((req, res) => {
  console.log(req.url, req.method, req.headers);
  res.setHeader('Content-Type', 'text/html');
  res.write('<html>');
  res.write('<head><title>Page</title></head>');
  res.write('<body><h1>Hello from my node.js</h1></body>')
  res.write('</html>');
  res.end();
  
});

server.listen(3000);