天国にいけるＣ言語入門 ヘキサ構造体 ver３.2128

まずはクイックソートのプログラムの構造でなく原理を学んでみよう

ソーラー「みんな

スーパークイックソートについては

爽快（リフレッシュ）できたかな？」

アレサ「はい😊

理解（リフレッシュ）しました

ソーラーさん」

ソーラー「ところで

配列変数に格納されている

数値を小さい順に入れ替えるってどうやったら

いいと思う？」

アレサ「？？？

配列変数に格納されている

数値を小さい順に入れ替える・・・ですの・・・？」

ソーラー「たとえば

0,1,2,3,4,5,6

という数値が

要素数が7のint型の配列hairetuの配列変数

hairetu[0]

hairetu[1]

hairetu[2]

hairetu[3]

hairetu[4]

hairetu[5]

hairetu[6]

にランダムに

hairetu[0]には2

hairetu[1]には1

hairetu[2]には0

hairetu[3]には3

hairetu[4]には6

hairetu[5]には5

hairetu[6]には4

と格納されているとします

このように

配列変数

hairetu[0]

hairetu[1]

hairetu[2]

hairetu[3]

hairetu[4]

hairetu[5]

hairetu[6]

に数値データが格納されている状態から

hairetu[0]には0

hairetu[1]には1

hairetu[2]には2

hairetu[3]には3

hairetu[4]には4

hairetu[5]には5

hairetu[6]には6

と

小さな数値データから順に数値データが格納されている状態に

並び替えるにはどうしたらいいと思う？」

アレサ「？？

その方法が

今までのエピソードで

やってきた

　　　　　　　バブルソート（整列、並び替え）

　　　　　　　スーパークイックソート

なのではないです・・・の？」

ソーラー「えへっ

今回は

　　　　　　　バブルソート（整列、並び替え）

　　　　　　　スーパークイックソート

は

使わないで

hairetu[0]には2

hairetu[1]には1

hairetu[2]には0

hairetu[3]には3

hairetu[4]には6

hairetu[5]には5

hairetu[6]には4

と数値データが格納されている状態から

hairetu[0]には0

hairetu[1]には1

hairetu[2]には2

hairetu[3]には3

hairetu[4]には4

hairetu[5]には5

hairetu[6]には6

と

小さな数値データから順に数値データが格納されている状態に

　　　　　　　　　　　　🌞クイックソート(整列、並び替え)🌞

と呼ばれる方法を用いて

並び変えてみたいと

思うんだ？」

アレサ「・・・

ええと？

　　　　　　　　　　　　🌞クイックソート(整列、並び替え)🌞

ですか

クイックは高速

という意味ですね

この

　　　　　　　　　　　　🌞クイックソート(整列、並び替え)🌞

という手法を用いれば

高速（短時間で）

hairetu[0]には2

hairetu[1]には1

hairetu[2]には0

hairetu[3]には3

hairetu[4]には6

hairetu[5]には5

hairetu[6]には4

と数値データが格納されている状態から

hairetu[0]には0

hairetu[1]には1

hairetu[2]には2

hairetu[3]には3

hairetu[4]には4

hairetu[5]には5

hairetu[6]には6

と

小さな数値データから順に配列変数に数値データが格納されている状態へ

数値データを入れ替えることができるのですか？」

ソーラー「そうなんだよ

他にも

バブルソート（整列、並び替え）

マージソート（整列、並び替え）

ヒープソート（整列、並び替え）

等があるんだけど

それらと比べても

　　　　　　　　　　　　🌞クイックソート(整列、並び替え)🌞

は

より高速（短時間で）

配列変数に格納されている数値データを入れ替えることができるんだ」

アレサ「素敵ですの

それでは　

　　　　　　　　　　　　🌞クイックソート(整列、並び替え)🌞

の解説を

ソーラーさん

お願いいたします」

ソーラー「まずは

　　　　　　　　　　　　🌞クイックソート(整列、並び替え)🌞

の

具体的なプログラムの解説でなく

　　　　　　　　　　　　🌞クイックソート(整列、並び替え)🌞

の

原理の解説と行こうかな

そのほうが簡単に

クイックソートプログラムを理解できるようになるんだよ

　　　　　　　　　　　　🌞クイックソート(整列、並び替え)🌞

の原理は

　　　　　　　　　　　　💖とても簡単なんだよ💖

　　　　　　　　　　　　　（本当です　　solarplexussより）

まず

2　6　0　3　1　5　4

という数値データがあるとします

この数値データを

0　1　2　3　4　5　6

という順番に並び変えてみたいと思います

さあ

どうやって並べ替えてみようかな？

まず

2　6　0　3　1　5　4

の数値データの中から１つ数値データを適当に選びます

たとえば

3なんかどうかな？

2　6　0　③　1　5　4

選んだね

ここで

③の左側に3より小さい数値を

③の右側に3より大きい数値を

集めて並べるんだ

順番は適当でいいよ

こんな感じかな

👇

2　0　1　③　6　5　4

これで第１段階終了

今度は

③の左側の数値2　0　1の部分だけについて考えてみるよ

③の左側の数値2　0　1の中から

適当に

数値を選びます

ここでは

0を選んでみるね

こんな感じかな

👇

2　0⃣　1 　③　6　5　4

ここで

0⃣の左側に0より小さい数値を

0⃣の右側に0より大きい数値を

集めて並べるんだ

0より小さい数値はないので

0⃣の左側に持ってくる数値はありません

0⃣の右側に0より大きい数値1,2

をもってきます

こんな感じかな

👇

0⃣　1 　2 　③　6　5　4

今度は

③の右側の数値6　5　4の部分だけに注目です

③の右側の数値6　5　4の中から

適当に

数値を選びます

ここでは

5を選んでみるね

こんな感じかな

👇

0⃣　1 　2 　③　6　5⃣　4

ここで

5⃣の左側に5より小さい数値を

5⃣の右側に5より大きい数値を

集めて並べるんだ

5より小さい数値は4なので

5⃣の左側に4を持ってきます

5⃣の右側に5より大きい数値6

をもってきます

こんな感じかな

👇

0⃣　1 　2 　③　4　5⃣　6

これで

第２段階終了だね」

アレサ「ソーラーさん

すでに

小さい数値から順に並び変えることができているのではないですか？」

ソーラー「そうなんだよ

だけど

ルール的には

（後ほど解説されます(^_-)-☆🌞）

1 　2

の部分に注目します

1 2の中から

適当に

数値を選びます

ここでは

1を選んでみるね

こんな感じかな

👇

0⃣　➊ 　2 　③　4　5⃣　6

ここで

➊の左側に1より小さい数値を

➊の右側に1より大きい数値を

集めて並べるんだ

➊より小さい数値はないので

➊の左側に持ってくる数値はありません

➊の右側には1より大きい数値2をもってきます

もともと

➊の右側には1より大きい数値2があるんだけどね

こんな感じかな

👇

0⃣　➊ 　2 　③　4　5⃣　6

何も変化してないって？

ともかく

これで

第３段階終了だね

えへへ

ただ単に

🌷　　🌷　　🌷　　🌷　　🌷　　🌷　　🌷

ある数値をえらんで

その左側に　そのある数値より小さい数値

その右側に　そのある数値より大きい数値

をあつめて適当に並べる

をくりかえす

ただそれだけで

🌷　　🌷　　🌷　　🌷　　🌷　　🌷　　🌷

なんだか(*^。^*)～

いつのまにやら

小さい数値から順に並び変えることができているね

最終的に

どの段階で並べ替えを終了するのか

が気になるよね　

もともとの数値データの集まりのなかから

適当に数値データを1つ選んで

その数値の右側と左側の部分に

数値データを分ける

さらに

その右側と左側の部分

それぞれの部分に注目する

その部分の中から

適当に１つ数値データを選んで

その数値の右側と左側の部分に

数値データを分ける

・

・

・

を繰り返すんだけど

数値データの集まりのなかから

適当に数値データを1つ選んで

その数値の右側と左側に数値データを振り分けた場合に

右側の部分にも左側の部分にも

2個の数値データが含まれていない場合に

並び替えを終了するんだよ

何も考えなくても

その時点で

ちゃんと小さな数値データから順に数値データは並ぶことになるんだよ

これが

クイックソートの原理なんだね

もう一回

すこしだけアプローチ方法をかえて

やってみるよ

2　6　0　3　1　5　4

という数値データがあるとします

この数値データを

0　1　2　3　4　5　6

という順番に並び変えてみたいと思います

さあ

どうやって並べ替えてみようかな？

まず

2　6　0　3　1　5　4

の数値データの中から１つ数値データを適当に選びます

たとえば

今度は

2なんかどうかな？」

アレサ「一番左端の数値ですか？」

ソーラー「そうなんだ

さて　うまくいくかな？

②　6　0　３　1　5　4

2を選んだね

ここで

②の左側に2より小さい数値を

②の右側に2より大きい数値を

集めて並べるんだ

順番は適当でいいんだよ

こんな感じかな

👇

0　1　②　3　6　5　4

これで第１段階終了

今度は

②の左側の数値0　1の部分だけについて考えてみるよ

②の左側の数値0　1の中から

適当に

数値を選びます

ここでは

0を選んでみるね

こんな感じかな

👇

0⃣　1　②　3　6　5　4

ここで

0⃣の左側に0より小さい数値を

0⃣の右側に0より大きい数値を

集めて並べるんだ

0より小さい数値はないので

0⃣の左側に持ってくる数値はありません

0⃣の右側に0より大きい数値1

をもってきます

こんな感じかな

👇

0⃣　1　②　3　6　5　4

って変化ありませんね

今度は

②の右側の数値3　6　5　4の部分だけに注目です

③の右側の数値3　6　5　4の中から

適当に

数値を選びます

ここでは

3を選んでみるね

こんな感じかな

👇

0⃣　1　②　3⃣　6　5　4

ここで

3⃣の左側に3より小さい数値を

3⃣の右側に3より大きい数値を

集めて並べるんだ

3より小さい数値はないので

3⃣の左側に持ってくる数値はありません

3⃣の右側に3より大きい数値6　5　4

をもってきます

こんな感じかな

👇

0⃣　1　②　3⃣　6　5　4

って変化なしだね

これで

第２段階終了だね」

ソーラー「

3⃣の右側に3より大きい数値6　5　4

が並んでいるね

今度は

この

6　5　4の中から

適当に

数値を選びます

ここでは

6を選んでみるね

こんな感じかな

👇

0⃣　1　②　3⃣　❻　5　4

ここで

❻の左側に6より小さい数値を

❻の右側に6より大きい数値を

集めて並べるんだ

❻の左側には6より小さい数値5,4をもってきます

❻の右側に持ってくる数値はありません

こんな感じかな

👇

0⃣　1　②　3⃣　5　4　❻　

これで

第３段階終了だね

さてさて

❻の左側に6より小さい数値5　4

が並んでいるね

今度は

この

5　4の中から

適当に

数値を選びます

ここでは

5を選んでみるね

こんな感じかな

👇

0⃣　1　②　3⃣　⑸　4　❻　

ここで

⑸の左側に5より小さい数値を

⑸の右側に5より大きい数値を

集めて並べるんだ

⑸の左側には5より小さい数値4を持ってきます

⑸の右側には持ってくる数値はありません

こんな感じかな

👇

0⃣　1　②　3⃣　4　⑸　❻　

これで第4段階終了

えへへ

なんと

何も考えなくても

0　1　2　3　4　5　6

と

小さな数値データから順にデータが並んだね

すごいなっ

結局のところ

ただ単に

🌷　　🌷　　🌷　　🌷　　🌷　　🌷　　🌷　　🌷　　🌷

ある数値をえらんで

その左側に　そのある数値より小さい数値

その右側に　そのある数値より大きい数値

をあつめて適当に数値データの集まりをつくる

その集められた数値データのあつまりから

ある数値をえらんで

その左側に　そのある数値より小さい数値

その右側に　そのある数値より大きい数値

をあつめて適当に数値データの集まりをつくる

をくりかえす

　　　　　　　　　　🌹ただそれだけで🌹

🌷　　🌷　　🌷　　🌷　　🌷　　🌷　　🌷　　🌷　　🌷

なんだか(*^。^*)～

いつのまにやら

0　1　2　3　4　5　6

と

小さい数値から順に並び変えることができているね

最終的に

どの段階で並べ替えを終了するのか

が気になるよね　

もともとの数値データの集まりのなかから

適当に数値データを1つ選んで

その数値の右側と左側の部分に

数値データを分ける

さらに

その右側と左側の部分

それぞれの部分の数値データの集まりに注目する

その数値データの集まりの中から

適当に１つ数値データを選んで

その数値の右側と左側の部分に

数値データを分ける

・

・

・

を繰り返すんだけど

数値データの集まりのなかから

適当に数値データを1つ選んで

分けられた

右側の部分にも左側の部分にも

2個の数値データを含んでいる部分がない場合に

並び替えを終了するんだよ

だから

❻の左側の部分に6より小さい数値5　4を持ってきた段階では

0⃣　1　②　3⃣　5　4　❻　

❻の左側の部分には6より小さい数値5　4が含まれているので

（つまり数値データが2つ含まれているので）

並び替えは終わらないんだ

だから

再び

5　4

から

適当に数値を1つ選んで並び替えをおこなうことになるんだね」