Algorithm, part 2

Sort

It is called sorting that you sort multiple data in a certain order. This is used

when you want to sort in ascending or descending order.

Below are some of the sorting algorithms.

（１）Insertion sort

This is a method of sorting by repeating the procedure of inserting elements

that have not been assigned yet in the correct position.

（２）Quick sort

Decide a reference value, divide it into large and small groups, and repeat this

to align.

（３）Selection sort

This is a method of sorting by repeating the procedure of finding the

maximum value (or minimum value) in the table.

（４）Bubble sort

Compare the values of adjacent elements and exchange if the magnitude is

reversed. This is a way to repeat this comparison until you no longer need it.

（５）Heap sort

Make the data into a heap structure and retrieve the first value of the data

when it is completed. Then, create a heap structure again, and so on.

Repeat this to sort.

（６）Shell sort

This is a sorting algorithm with improved insertion sort. Swap the distant

elements in the list in advance, and finally perform the insertion sort.

（７）Merge sort

Sorting is performed by recursively dividing the array you want to sort and

merging it again.

Let's take a closer look at insertion sort.

Insertion sort

Insertion sort sorts by comparing the data and inserting it in the appropriate

position. The idea of insertion sort is as follows.

For example, if you want to sort an array with 5 arbitrary data in ascending

order by insertion sort, it is as follows.

① Compare the data in the subscripts 0 and 1. In the case of the figure below, 50 is larger than 10, so they are not replaced.

②Compare the data in subscripts 1 and 2.

③50 is larger than 40, so replace them.

④Compare the data in subscripts 0 and 1. 10 is smaller than 40, so do not

replace them.

⑤Compare the data in subscripts 2 and 3.

⑥50 is larger than 20, so replace them.

⑦Compare the data in subscripts 1 and 2.

⑧40 is larger than 20, so replace them.

⑨Compare the data in subscripts 0 and 1. 10 is smaller than 20, so do not

replace them.

⑩Compare the data in subscripts 3 and 4.

⑪50 is larger than 30, so replace them.

⑫Compare the data in subscripts 2 and 3.

⑬40 is larger than 30, so replace them.

⑭Compare the data in subscripts 1 and 2. 20 is smaller than 30, so do not

replace them.

⑮Compare the data in subscripts 0 and 1. 10 is smaller than 20, so do not

replace them.

Insertion sort has done, and the data has become in ascending order.

Next, let's take a look at the insertion sort algorithm.

For example, if you want to sort an array with 5 numbers in ascending order

by insertion sort:

【Algorithm】

①Let 1 be the comparison target (right side).

 （The first comparison is for the subscripts 0 and 1）

②Repeat the following while the comparison target (right side) is no more

　than 4.

　②-1.　The comparison target (left side) shall be the value obtained by

　　　　comparison target (right side) -1.

　②-2.　Repeat the following while the comparison target (left side) is not

　　　　less than 0.

　　②-2-1.　If array[comparison target (left side)] ＞

　　　　　　array[comparison target (right side)], they replace each other.

　　②-2-2.　The comparison target (left side) -1.

 　②-3.　The comparison target (right side) +1.

This algorithm sorts the array in ascending order.

---

[Japanese]

整列のアルゴリズム

複数のデータを一定の順序に並べ替えることを整列（ソート）といいます。

昇順や降順に並べ替えるときに利用します。

整列のアルゴリズムの一部を下記に紹介します。

（１）挿入ソート

まだ整列済みでない要素を正しい位置へ挿入する手続きを繰り返すことにより並べ替える方法です。

（２）クイックソート

基準値を決めて大小のグループに分割し、これを繰り返して整列を行います。

（３）選択ソート

最大値（または最小値）をテーブルの中から見つける手続きを繰り返すことにより並べ替える方法です。

（４）バブルソート

隣り合う要素の値を比較し、大小が逆だったら交換します。この比較を必要がなくなるまで繰り返す方法です。

（５）ヒープソート

データをヒープ構造にし、完成したらデータの先頭の値を取り出します。

そしてまたヒープ構造を作り・・・という繰り返しで整列を行います。

（６）シェルソート

シェルソートは挿入ソートが改良された整列アルゴリズムです。リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行します。

（７）マージソート

並べ替えたい配列を再帰的に分割していき、再び併合（マージ）していくことで、整列を行います。

これらの中から、挿入ソートについて詳しく見ていきましょう。

挿入ソート

挿入ソートは、データを比較して適切な位置に挿入することで並び替えます。挿入ソートの考え方は、次のようになります。

（例）5個の任意のデータを持つ配列を、挿入ソートで昇順に並び替える場合

①添字の0と1にあるデータを比較します。下図の場合、10よりも50の方が大きいので、並び替えはしません。

②添字の1と2にあるデータを比較します。

③40よりも50の方が大きいので、入れ替えます。

④添字の0と1を比較します。40よりも10の方が小さいので、入れ替えません。

⑤添字の2と3を比較します。

⑥20よりも50の方が大きいので、入れ替えます。

⑦添字の1と2を比較します。

⑧20よりも40の方が大きいので、入れ替えます。

⑨添字の0と1を比較します。20よりも10の方が小さいので、入れ替えません。

⑩添字の3と4を比較します。

⑪30よりも50の方が大きいので、入れ替えます。

⑫添字の2と3を比較します。

⑬30よりも40の方が大きいので、入れ替えます。

⑭添字の1と2を比較します。30よりも20の方が小さいので、入れ替えません。

⑮添字の0と1を比較します。20よりも10の方が小さいので、入れ替えません。

これで挿入ソートによる並べ替えが完了し、昇順になりました。

続いて、挿入ソートのアルゴリズムを見てみましょう。

（例）5つの数値が記録された配列を、挿入ソートで昇順に並べ替える

【アルゴリズム】

①比較対象(右側)を1とする。（最初の比較は添字の0と1のため）

②比較対象(右側)が4以下の間、下記を繰り返す。

　②-1.　比較対象(左側)は、比較対象(右側) - 1 した値とする。

　②-2.　比較対象(左側)が0以上の間、下記を繰り返す。

　　②-2-1.　配列[比較対象(左側)]　＞　配列[比較対象(右側)]の場合、

　　　　　　配列[比較対象(左側)] と 配列[比較対象(右側)] のデータを

　　　　　　入れ替える。

　　②-2-2.　比較対象(左側)の値を -1 する。

 　②-3.　比較対象(右側)の値を +1 する。

このアルゴリズムによって、昇順に並び替わります。