pontz_rwのブログ

プログラミング等の備忘録

Markdown記法

Markdown は文章を記述するための記法の一つです。

このブログの記事も普段から Markdown記法を用いて作成されていますが、この機会に簡単にまとめてみました。

Markdwon記法

複数の記法が利用できる場合もあります。

段落

段落は空行によって分けられます。

記述例

あいうえお。かきくけこ。

さしすせそ。

次のように表示されます。

あいうえお。かきくけこ

さしすせそ。

見出し

見出しは行頭に「#」とスペースを置きます。「#」の数が見出しのレベルに対応しており、1~6まであります。

記述例

# 見出し1

## 見出し2

### 見出し3

#### 見出し4

##### 見出し5

###### 見出し6

次のように表示されます。

見出し1

見出し2

見出し3

見出し4

見出し5
見出し6

強調

強調したい文字を「*」で囲みます。通常、「*」1個で囲うと斜体、2個で囲うと太字で表示されます。「*」ではなく「_」でも同様です。

記述例

_italic_ or **bold**.

次のように表示されます。

italic or bold.

箇条書きリスト

箇条書きリストは行頭に「*」とスペースを置きます。「*」ではなく「-」でも同様です。

記述例

* リスト1
* リスト2
    * リスト2-1
    * リスト2-2
* リスト3

次のように表示されます。

  • リスト1
  • リスト2
    • リスト2-1
    • リスト2-2
  • リスト3

番号付きリスト

箇条書きリストは行頭に数字とスペースを置きます。番号は表示される際に適切な番号で表示されるので、すべて 1. ~ のような形式で記載すると良いです。

記述例

1. リスト1
1. リスト2
    1. リスト2-1
    1. リスト2-2
1. リスト3

次のように表示されます。

  1. リスト1
  2. リスト2
    1. リスト2-1
    2. リスト2-2
  3. リスト3

コードブロック

コードブロックは単一行であれば文字を「`」で囲います。複数行の場合は「```」を前後の行に置きます。

これまでの文章においても、記述例にコードブロックを利用しています。

記述例

python 3 で `Hello, world!` を出力するには、以下のように記述します。

​```
print("Hello, world!")
​```

次のように表示されます。

python 3 で Hello, world! を出力するには、以下のように記述します。
print("Hello, world!")

引用

引用は行頭に「>」を置きます。

これまでの文章においても、記述例に対する表示結果に引用を利用しています。

記述例

> 引用

次のように表示されます。

引用

リンク

リンクしたいテキストを「[]」で囲み、それに続いてリンク先URLを「()」で囲います。

記述例

[pontz_rwのブログ](http://pontz-rw.hatenablog.jp/)

次のように表示されます。

pontz_rwのブログ

INTERSECTとEXCEPT

UNION (和集合) を勉強したついでに、INTERSECT (積集合) と EXCEPT (差集合) についても学んでいきます。

これら2つは UNION と同様に、2つのテーブルから1つのテーブルを出力します。2つのテーブルは列数と各列の型を揃える必要があります。

INTERSECT

INTERSECT は、2つのテーブルに含まれる行を取得します。

次のような単一の列を持つ2つのテーブルA、Bがあるとします。


A = \{ 2, 4, 6, 8, 10 \}\\
B = \{ 1, 1, 2, 3, 5, 8 \}

このとき、2つのテーブルに含まれる行からなるテーブルをCとすると、Cは次のようになります。


A \cap B = C = \{ 2, 8 \}

実際に INTERSECT を使ってみましょう。

-- A
SELECT i
  FROM (VALUES (2), (4), (6), (8), (10)) AS A(i)

INTERSECT

-- B
SELECT i
  FROM (VALUES (1), (1), (2), (3), (5), (8)) AS B(i)
i
2
8

AとBに共通する2と8が取得されます。

テーブル内に重複行を持つB同士で INTERSECT するとどうなるのでしょうか。実際に試してみましょう。

-- B
SELECT i
  FROM (VALUES (1), (1), (2), (3), (5), (8)) AS B(i)

INTERSECT

-- B
SELECT i
  FROM (VALUES (1), (1), (2), (3), (5), (8)) AS B(i)

結果は次の通りです。重複する1は1行のみ出力されています。

i
1
2
3
5
8

これらの結果は、AとBをINNER JOINで結合した結果とほとんど変わりません。キーがない場合などはうまくいきません。

SELECT A.i
  FROM (VALUES (2), (4), (6), (8), (10)) AS A(i)
       INNER JOIN
       (VALUES (1), (1), (2), (3), (5), (8)) AS B(i)
          ON A.i = B.i

EXCEPT

EXCEPTは差集合を表し、2番目のテーブルに含まれる行を取り除いた結果を表示します。

先ほどと同じ、単一の列を持つ2つのテーブルA、Bがあるとします。


A = \{ 2, 4, 6, 8, 10 \}
\\
B = \{ 1, 1, 2, 3, 5, 8 \}

このとき、AからBに存在する行を取り除いた結果からなるテーブルをCとすると、Cは次のようになります。


A - B = C = \{ 4, 6, 10 \}

AとBの関係を逆にした場合も、共通行となる 2 と 8 が取り除かれます。ただし、Bに存在する重複行は削除されます。


B - A = C = \{ 1, 3, 5 \}

実際に EXCEPT を使ってみましょう。まずは A EXCEPT B です。

-- A
SELECT i
  FROM (VALUES (2), (4), (6), (8), (10)) AS A(i)

EXCEPT

-- B
SELECT i
  FROM (VALUES (1), (1), (2), (3), (5), (8)) AS B(i)
i
4
6
10

続いて、B EXCEPT A を試してみましょう。

-- B
SELECT i
  FROM (VALUES (1), (1), (2), (3), (5), (8)) AS B(i)

EXCEPT

-- A
SELECT i
  FROM (VALUES (2), (4), (6), (8), (10)) AS A(i)
i
1
3
5

これらの結果は、次のように LEFT OUTER JOIN を使って結合した場合とほとんど同じです。キーがない場合などはうまくいきません。

-- A EXCEPT B
SELECT A.i
  FROM (VALUES (2), (4), (6), (8), (10)) AS A(i)
       LEFT OUTER JOIN
       (VALUES (1), (1), (2), (3), (5), (8)) AS B(i)
          ON A.i = B.i
 WHERE B.i IS NULL

結合条件 A.i = B.i に一致しないBの行については NULL になるので、B.iNULL の行のみを取得することで共通行を除いた結果が取得できます。

小計、合計行を出力する

小計行や合計行を出力したい場合に ROOLUP を使用できます。

次のようなデータを使って ROLLUP の動作を見ていきます。

SELECT sale_id,
       area_id,
       amount
  FROM (VALUES ('S001', 'A001', 100),
               ('S001', 'A002', 150),
               ('S001', 'A003', 100),
               ('S002', 'A001', 100),
               ('S002', 'A002', 150),
               ('S003', 'A001', 200)) AS Sales(sale_id, area_id, amount)
sale_id area_id amount
S001 A001 100
S001 A002 150
S001 A003 100
S002 A001 100
S002 A002 150
S003 A001 200

売上一覧と sale_id 別の売上

まずは売上一覧と sale_id 別の売上を同時に取得してみましょう。次のような取得結果を目指します。

sale_id area_id amount
S001 A001 100
S001 A002 150
S001 A003 100
S001 350
S002 A001 100
S002 A002 150
S002 250
S003 A001 200
S003 200

一般的には売上一覧と sale_id 別の売上を別々に取得し、UNION で結合して取得します。

WITH Sales AS
(SELECT sale_id,
        area_id,
        amount
   FROM (VALUES ('S001', 'A001', 100),
                ('S001', 'A002', 150),
                ('S001', 'A003', 100),
                ('S002', 'A001', 100),
                ('S002', 'A002', 150),
                ('S003', 'A001', 200)) AS Sales(sale_id, area_id, amount))
-- 売上一覧
SELECT sale_id,
       area_id,
       amount
  FROM Sales
 UNION ALL
-- sale_id 別売上
SELECT sale_id,
       NULL AS area_id,
       SUM (amount) AS amount
  FROM Sales
 GROUP BY sale_id
 ORDER BY sale_id,
          area_id NULLS LAST

ORDER BY 句で sale_id 別の売上が、対応する sale_id の末尾にくるように調整しています。

では、ROLLUP を使って上記のクエリと同じ結果を取得してみましょう。

WITH Sales AS
(SELECT sale_id,
        area_id,
        amount
   FROM (VALUES ('S001', 'A001', 100),
                ('S001', 'A002', 150),
                ('S001', 'A003', 100),
                ('S002', 'A001', 100),
                ('S002', 'A002', 150),
                ('S003', 'A001', 200)) AS Sales(sale_id, area_id, amount))
SELECT sale_id,
       area_id,
       SUM (amount) AS amount
  FROM Sales
 GROUP BY sale_id,
          ROLLUP (area_id)
 ORDER BY sale_id,
          area_id NULLS LAST

UNION を使ったクエリとの違いは、次の通りです。

  WITH Sales AS
  (SELECT sale_id,
          area_id,
          amount
     FROM (VALUES ('S001', 'A001', 100),
                  ('S001', 'A002', 150),
                  ('S001', 'A003', 100),
                  ('S002', 'A001', 100),
                  ('S002', 'A002', 150),
                  ('S003', 'A001', 200)) AS Sales(sale_id, area_id, amount))
- SELECT sale_id,
-        area_id,
-        amount
-   FROM Sales
-  UNION ALL
  SELECT sale_id,
-        NULL AS area_id,
+        area_id,
         SUM (amount) AS amount
    FROM Sales
-  GROUP BY sale_id
+  GROUP BY sale_id,
+           ROLLUP (area_id)
   ORDER BY sale_id,
            area_id NULLS LAST

sale_id ごとの小計を取得する場合は、ROLLUP (sale_id) ではなく ROLLUP (area_id) を使うので、注意しましょう。

sale_id ごとの売上と総売上

続いて sale_id ごとの売上と総売上を取得してみましょう。

WITH Sales AS
(SELECT sale_id,
        area_id,
        amount
   FROM (VALUES ('S001', 'A001', 100),
                ('S001', 'A002', 150),
                ('S001', 'A003', 100),
                ('S002', 'A001', 100),
                ('S002', 'A002', 150),
                ('S003', 'A001', 200)) AS Sales(sale_id, area_id, amount))
-- sale_id 別売上
SELECT sale_id,
       SUM (amount) AS amount
  FROM Sales
 GROUP BY sale_id
 UNION ALL
-- 総売上
SELECT NULL AS sale_id,
       SUM (amount) AS amount
  FROM Sales
 ORDER BY sale_id NULLS LAST
sale_id amount
S001 350
S002 250
S003 200
800

ROLLUP を使って同じ結果を取得してみましょう。

WITH Sales AS
(SELECT sale_id,
        area_id,
        amount
   FROM (VALUES ('S001', 'A001', 100),
                ('S001', 'A002', 150),
                ('S001', 'A003', 100),
                ('S002', 'A001', 100),
                ('S002', 'A002', 150),
                ('S003', 'A001', 200)) AS Sales(sale_id, area_id, amount))
SELECT sale_id,
       SUM (amount) AS amount
  FROM Sales
 GROUP BY ROLLUP (sale_id)
 ORDER BY sale_id NULLS LAST

UNION を使ったクエリとの違いは、次の通りです。

  WITH Sales AS
  (SELECT sale_id,
          area_id,
          amount
     FROM (VALUES ('S001', 'A001', 100),
                  ('S001', 'A002', 150),
                  ('S001', 'A003', 100),
                  ('S002', 'A001', 100),
                  ('S002', 'A002', 150),
                  ('S003', 'A001', 200)) AS Sales(sale_id, area_id, amount))
  SELECT sale_id,
         SUM (amount) AS amount
    FROM Sales
-  GROUP BY sale_id
+  GROUP BY ROLLUP (sale_id)
-  UNION ALL
- SELECT NULL AS sale_id,
-        SUM (amount) AS amount
-   FROM Sales
   ORDER BY sale_id NULLS LAST

GROUP BY ROLLUP (sale_id)sale_id 別の売上と、それらをまとめた総売上を求めるのに必要であることが分かります。

これまでの結果をまとめる

では、最後にこれまでの結果をまとめたものを取得するクエリを、ROLLUP を使って求めてみましょう。次のような取得結果を目指します。

sale_id area_id amount
S001 A001 100
S001 A002 150
S001 A003 100
S001 350
S002 A001 100
S002 A002 150
S002 250
S003 A001 200
S003 200
800

sale_idarea_id の2つを ROLLUP に指定します。

WITH Sales AS
(SELECT sale_id,
        area_id,
        amount
   FROM (VALUES ('S001', 'A001', 100),
                ('S001', 'A002', 150),
                ('S001', 'A003', 100),
                ('S002', 'A001', 100),
                ('S002', 'A002', 150),
                ('S003', 'A001', 200)) AS Sales(sale_id, area_id, amount))
SELECT sale_id,
       area_id,
       SUM (amount) AS amount
  FROM Sales
 GROUP BY ROLLUP (sale_id,
                  area_id)
 ORDER BY sale_id,
          area_id NULLS LAST

以上より sale_id 別の小計と合計を同時に取得することができます。

見た目を整える

集計行の集計キーは NULL となるので、COALESCE() を使うなどして見た目を整えることもできます。

SELECT COALESCE(sale_id, '') AS sale_id,
       COALESCE(area_id, CASE
                         WHEN sale_id IS NULL THEN '合計'
                         ELSE '小計'
                         END) AS area_id,
       SUM(amount) AS amount
  FROM (VALUES ('S001', 'A001', 100),
               ('S001', 'A002', 150),
               ('S001', 'A003', 100),
               ('S002', 'A001', 100),
               ('S002', 'A002', 150),
               ('S003', 'A001', 200)) AS Sales(sale_id, area_id, amount)
 GROUP BY ROLLUP (sale_id, area_id)
sale_id area_id amount
S001 A001 100
S001 A002 150
S001 A003 100
S001 小計 350
S002 A001 100
S002 A002 150
S002 小計 250
S003 A001 200
S003 小計 200
合計 800

また GROUPING() を使うことで、どの行が集計行であるのかが分かります。

SELECT GROUPING(sale_id) AS total_sum,
       GROUPING(area_id) AS sale_id_sum,
       CASE WHEN GROUPING(sale_id) = 1 THEN ''
            ELSE sale_id
       END AS sale_id,
       CASE WHEN GROUPING(sale_id) = 1 THEN '合計'
            WHEN GROUPING(area_id) = 1 THEN '小計'
            ELSE area_id
       END AS area_id,
       SUM(amount) AS amount
  FROM (VALUES ('S001', 'A001', 100),
               ('S001', 'A002', 150),
               ('S001', 'A003', 100),
               ('S002', 'A001', 100),
               ('S002', 'A002', 150),
               ('S003', 'A001', 200)) AS Sales(sale_id, area_id, amount)
 GROUP BY ROLLUP (sale_id, area_id)
total_sum sale_id_sum sale_id area_id amount
0 0 S001 A001 100
0 0 S001 A002 150
0 0 S001 A003 100
0 1 S001 小計 350
0 0 S002 A001 100
0 0 S002 A002 150
0 1 S002 小計 250
0 0 S003 A001 200
0 1 S003 小計 200
1 1 合計 800

UNION と UNION ALL の違い

どっちがどっちだかよく忘れてしまうので、まとめます。

結論から言うと、UNION ALL は重複行を許しますが、UNION は除外します。

UNIONとは

UNION は2つのテーブルを結合して1つのテーブルを生成します。結合するテーブルは、次の条件を満たす必要があります。

  1. 2つのテーブルが同じ列数であること
  2. 同じ位置にある列は、同じデータ型であること

UNION と UNION ALL の違い

UNION と UNION ALL の違いは、重複行の扱いです。

UNION は、重複行を除外します。対して、UNION ALL は重複行を許します。そのため、重複行を含むテーブルに対しての UNION と UNION ALL では、取得結果が変わります。

また、UNION では重複行を除外する分、処理が遅くなる可能性があります。重複するデータがないことが予め分かっている場合や、重複を気にしない場合は、UNION ALL を使用するほうが良いです。

2つの集合A、Bに対して UNION と UNION ALL を使ってみましょう。

Aは、1 ~ 10 までの整数のうち、2の倍数からなります。

SELECT i
  FROM (VALUES (2), (4), (6), (8), (10)) AS A(i)
i
2
4
6
8
10

Bは、1 ~ 10 までの整数のうち、フィボナッチ数列を満たす数からなります。

SELECT i
  FROM (VALUES (1), (1), (2), (3), (5), (8)) AS B(i)
i
1
1
2
3
5
8

まずは、UNION を使ってみましょう。

-- A
SELECT i
  FROM (VALUES (2), (4), (6), (8), (10)) AS A(i)

 UNION

-- B
SELECT i
  FROM (VALUES (1), (1), (2), (3), (5), (8)) AS B(i)
i
1
2
3
4
5
6
8
10

図は分かりやすいように結果をソートしています。

結果を見てわかるように、AとBの間で重複している2と8、Aの中で重複している1が、それぞれ1行のみ出力されています。

続いて、UNION ALL を使ってみましょう。

-- A
SELECT i
  FROM (VALUES (2), (4), (6), (8), (10)) AS A(i)

 UNION

-- B
SELECT i
  FROM (VALUES (1), (1), (2), (3), (5), (8)) AS B(i)
i
1
1
2
2
3
4
5
6
8
8
10

重複している行がそのまま出力されています。

「賢者の石」によるジェム稼ぎ

有名な方法ですが、ジェムを稼ぐ方法として「賢者の石」をジェム還元する方法があります。

賢者の石が作成できない時点では、メイプルデルタの木を伐採して獲得した素材をジェム還元していました。

  1. メイプルデルタ「香る蜜木の森」へ移動
  2. すぐに直前のマップ「甘露川ほとり」へエリア移動
  3. 近くの木を2本伐採

持ち物がいっぱいになるまで繰り返し、獲得した素材を全てジェム還元して5万ジェム程度獲得していました。

「賢者の石」によるジェム還元では、この方法とは比べ物にならないくらい効率的にジェムを獲得できます。

「賢者の石」の派生元

ストーリーをクリアした人であればすぐに「賢者の石」を作成できる状態にあると思いますが、一応、レシピ派生の流れを確認します。

  1. ミックスオイル
  2. アルケミーペイント
  3. 精霊の小瓶
  4. クリスタルエレメント
  5. 賢者の石

漏れがなければこの順番で派生していきます。ですので、「クリスタルエレメント」まで作成できる状態にしておきましょう。

準備

  1. 作成個数+2 を発動させた「赤の輝石」
  2. 最低3万ジェム程度

「賢者の石」を作成するにあたって必要となるのは「赤の輝石」です。ジェム還元を効率化するには 作成個数+2 の効果を発動させる必要があります。作成個数+2 の効果を発動させた「赤の輝石」を1つ作成しましょう。

「赤の輝石」作成に当たって、「異界のコア」、「禁忌の雫」、「聖なる雫」が必要です。

また、この「赤の輝石」を複製する工程があります。2回目以降は「賢者の石」を還元して得たジェムを使用するので良いのですが、最初の一回は自前で「赤の輝石」複製することになります。1個複製するのに3万前後必要ですので、不要な素材をジェム還元しておきましょう。

ジェム還元の手順

  1. 作成個数+2 の効果を発動させた「赤の輝石」を複製
  2. 複製した「赤の輝石」をもとに、「賢者の石」を作成
  3. 作成した「賢者の石」をジェム還元

この手順を満足いくまで繰り返すことで、効率的にジェムを獲得することができます。まさに錬金術ですね。

注意点としては、複製元となる「赤の輝石」が1個必要となります。「賢者の石」を作成する際は、所持しているすべての「赤の輝石」を投入せず、複製元となる1個は残すようにしましょう。

加えて、「赤の輝石」のみを素材にして作成することができるので、他の素材を取りに行く手間がかかりません。また、錬金レベル上げにも使えます。

まとめ

「賢者の石」によるジェム還元はジェム獲得と錬金レベル上げを効率的に行う良い方法です。多くの方にとっては既知の情報でしょうが、まだ知らなかった方は、ぜひ試してみてください。

Ruby on Rails Tutorial のナビゲーションバーを Bootstrap 4 で作る

Ruby on Rails Tutorialの 5.1.1 ナビゲーション では、Bootstrap 3 を用いてナビゲーションバーを作成しています。2018年12月現在、Bootstrap 4 が最新となります。

バージョンの違いにより、ナビゲーションバーがうまく表示されないため、以下では、Bootstrap 4 を用いて、それっぽいナビゲーションバーをhtmlで作成していきます。

作成準備

公式ホームページの Starter template を使い、雛型を作成します。

  • index.html
<!doctype html>
<html lang="ja">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.1.3/css/bootstrap.min.css" integrity="sha384-MCw98/SFnGE8fJT3GXwEOngsV7Zt27NXFoaoApmYm81iuXoPkFOJwJ8ERdknLPMO" crossorigin="anonymous">
    <title>Ruby on Rails Tutorial</title>
  </head>
  <body>
    <header>
      <nav>
        <a id="logo">sample app</a>
        <ul>
          <li><a href="#">Home</a></li>
          <li><a href="#">Help</a></li>
          <li><a href="#">Log in</a></li>
        </ul>
      </nav>
    </header>
    <h1>Hello, world!</h1>
    <script src="https://code.jquery.com/jquery-3.3.1.slim.min.js" integrity="sha384-q8i/X+965DzO0rT7abK41JStQIAqVgRVzpbzo5smXKp4YfRvH+8abtTE1Pi6jizo" crossorigin="anonymous"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.14.3/umd/popper.min.js" integrity="sha384-ZMP7rVo3mIykV+2+9J3UJ46jBk0WLaUAdn689aCwoqbBJiSnjAK/l8WvCWPIPm49" crossorigin="anonymous"></script>
    <script src="https://stackpath.bootstrapcdn.com/bootstrap/4.1.3/js/bootstrap.min.js" integrity="sha384-ChfqqxuZUCnJSK3+MXmPNIyE6ZbWh2IMqE241rYiqJxyMiZ6OW/JmZQ5stwEULTy" crossorigin="anonymous"></script>
  </body>
</html>

作成開始

装飾していきます。

navタグにクラスを指定

まず、ナビゲーションバーには、.navbarnavbar-expand を設定します。

次に、明るい背景色 .navbar-light か、暗い背景色 .navbar-dark のどちらかを設定し、背景色として .bg-* を設定します。

そして、画面上部に固定するために、.fixed-top を設定します。

<nav class="navbar navbar-expand-md navbar-dark fixed-top bg-dark">
  ...
</nav>

Hello, world! がナビゲーションバーで隠れてしまうので、やや強引ですが、余白を設定します。

<body class="mt-5 pt-5">
  ...
</body>

ロゴ

.navbar-brand を設定します。

大文字にするために .text-uppercase を、太字にするために .font-weight-bold を設定しています。

<a class="navbar-brand text-uppercase font-weight-bold" href="#">sample app</a>

ナビゲーションコンポーネント

ul.navbar-navli.nav-itema.nav-link をそれぞれ設定します。

<ul class="navbar-nav">
  <li class="nav-item"><a class="nav-link" href="#">Home</a></li>
  <li class="nav-item"><a class="nav-link" href="#">Help</a></li>
  <li class="nav-item"><a class="nav-link" href="#">Log in</a></li>
</ul>

ロゴとナビゲーションコンポーネントとの間にスペースを空ける

フレックスユーティリティクラスを使用することで、ナビゲーションの右寄せ .justify-content-end や中央寄せ .justify-content-center などができます。

<nav class="navbar navbar-expand navbar-dark fixed-top bg-dark justify-content-between">
  ...
</nav>

完成

以上で完成となります。

  • index.html
<!doctype html>
<html lang="ja">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.1.3/css/bootstrap.min.css" integrity="sha384-MCw98/SFnGE8fJT3GXwEOngsV7Zt27NXFoaoApmYm81iuXoPkFOJwJ8ERdknLPMO" crossorigin="anonymous">
    <title>Ruby on Rails Tutorial</title>
  </head>
  <body class="mt-5 pt-5">
    <header>
      <nav class="navbar navbar-expand navbar-dark fixed-top bg-dark justify-content-between">
        <a class="navbar-brand text-uppercase font-weight-bold" href="#">sample app</a>
        <ul class="navbar-nav">
          <li class="nav-item"><a class="nav-link" href="#">Home</a></li>
          <li class="nav-item"><a class="nav-link" href="#">Help</a></li>
          <li class="nav-item"><a class="nav-link" href="#">Log in</a></li>
        </ul>
      </nav>
    </header>
    <h1>Hello, world!</h1>
    <script src="https://code.jquery.com/jquery-3.3.1.slim.min.js" integrity="sha384-q8i/X+965DzO0rT7abK41JStQIAqVgRVzpbzo5smXKp4YfRvH+8abtTE1Pi6jizo" crossorigin="anonymous"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.14.3/umd/popper.min.js" integrity="sha384-ZMP7rVo3mIykV+2+9J3UJ46jBk0WLaUAdn689aCwoqbBJiSnjAK/l8WvCWPIPm49" crossorigin="anonymous"></script>
    <script src="https://stackpath.bootstrapcdn.com/bootstrap/4.1.3/js/bootstrap.min.js" integrity="sha384-ChfqqxuZUCnJSK3+MXmPNIyE6ZbWh2IMqE241rYiqJxyMiZ6OW/JmZQ5stwEULTy" crossorigin="anonymous"></script>
  </body>
</html>

ALDS1_1_A: 挿入ソート

問題

解答

問題文に記載されている挿入ソートのアルゴリズムを実装します。出力は、ソート前に 1 回と、各計算ステップの途中経過を N - 1 回の、合計 N 回行います。

C++

#include <iostream>
using namespace std;

const int MAX_N = 100;

// 配列の要素を出力
void trace(int (&A)[MAX_N], int N) {
    for (int i = 0; i < N; ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << A[i];
    }
    cout << endl;
}

// 挿入ソート
void insertionSort(int (&A)[MAX_N], int N) {
    for (int i = 1; i < N; ++i) {
        int v = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > v) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = v;
        trace(A, N);
    }
}

int main() {
    int N;
    int A[MAX_N];

    // 入力
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // 配列の要素を出力
    trace(A, N);

    // 挿入ソート
    insertionSort(A, N);

    return 0;
}

Python

# coding: utf-8

N = int(input())
A = list(map(int, input().split()))

print(*A)

for i in range(1, len(A)):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j + 1] = A[j]
        j -= 1
    A[j + 1] = v
    print(*A)