[CpawCTF] 第九夜: ソート (バブルソート)
Q14.[PPC]並べ替えろ!
以下、問題文
Q14.[PPC]並べ替えろ!
10pt
下にある配列の中身を大きい順に並べ替えて、くっつけてcpaw{並べ替えた後の値}をフラグとして提出してください。
例：もし配列｛1,5,3,2｝っていう配列があったら、大きい順に並べ替えると｛5,3,2,1}となります。
そして、フラグはcpaw{5321}となります。
同じようにやってみましょう（ただし量が多いので、ソートするプログラムを書いたほうがいいですよ！）
[15,1,93,52,66,31,87,0,42,77,46,24,99,10,19,36,27,4,58,76,2,81,50,102,33,94,20,14,80,82,49,41,12,143,121,7,111,100,60,55,108,34,150,103,109,130,25,54,57,159,136,110,3,167,119,72,18,151,105,171,160,144,85,201,193,188,190,146,210,211,63,207]
答案
今回は正整数がたくさん連なっている配列が与えられており、これを降順 (大きい順) に並べ、結合した文字列が Flag になるらしいです。
ちょっと配列のサイズ的に力技で (紙の上とか、手作業で) 並べ替えるのは面倒なので、 問題文のヒントにしたがって、ソートをするプログラムを書いていこうと思います。
ソートに関しては、コンピュータを使っていく上で、様々議論がなされてきた分野です。
いくつかの方法があり、それぞれに特色があったりします。 これに関しては様々な方がすでに詳細な解説や、プログラムの例を掲載してくださっておりますので、 それぞれのソート方法に関する深堀はしません。
そもそも、先に書いておられる方々を凌駕できるほど、 明快で正しい説明ができる知識を持っている自信がありませんし...
いくつか参考を載せさせていただくことでご容赦ください。
今回は「記述が簡単で読みやすい」という点と、「実装しやすい(プログラムとして書きやすい)」ことから 「バブルソート」と呼ばれるアルゴリズムを使って、配列をソートしていこうと思います。
バブルソート
バブルソートは、配列内の各々の数字に着目して、その隣同士の大小関係をいちいち比較することで 最終的に配列全体を大小の順番に並べることを達成する、というソート方法です。
書き方や、仕組みが理解しやすいという利点の代わりに、 ソート完了までかかる時間が比較的長い、という欠点を被ることになります。
この辺はトレードオフの関係になっているので、仕方ないでしょう。
バブルソートの「バブル」とは、我々のよく知る「泡」のバブルのことで、 配列の要素を比較し、入れ替える際に、大小関係が入れ替わり、 泡のように底から表面にポワポワと浮いてくるイメージから名前がついているようです。
イメージとしては こちらの動画 がとてもわかりやすいかと思います。
プログラム
ソースコードに関しては、こちら を参考にさせていただきました。
前回 (第2夜?) 同様、C言語で テキトーに 書いてみます。
/* バブルソート */ #include <stdio.h> int main() { printf("program starts.\n"); int A[] = {15,1,93,52,66,31,87,0,42,77,46,24,99,10,19,36,27,4,58,76,2,81,50,102,33,94,20,14,80,82,49,41,12,143,121,7,111,100,60,55,108,34,150,103,109,130,25,54,57,159,136,110,3,167,119,72,18,151,105,171,160,144,85,201,193,188,190,146,210,211,63,207}; int mem_sz = sizeof(A); int mem_sz_one = sizeof(A[0]); int nelem = mem_sz / mem_sz_one; printf("memory size all:%d / one:%d\n", mem_sz, mem_sz_one); printf("array elements: %d\n", nelem); // ソート前の配列の確認 printf("before = {"); for (int i=0; i<nelem; i++) { printf("%d", A[i]); if (i!=nelem-1) { printf(", "); } } printf("}\n"); // バブルソートを実行 int tmp; for (int i=0; i<nelem; i++) { for (int j=i+1; j<nelem; j++) { if (A[i] > A[j]) { tmp = A[j]; A[j] = A[i]; A[i] = tmp; } } } // ソート後のリストを確認 printf("sorted list = {"); for (int i=0; i<nelem; i++) { printf("%d", A[i]); if (i!=nelem-1) { printf(", "); } } printf("}\n"); // flag の出力 // 大きい順で出力することに注意 printf("The flag is below:\n"); printf("cpaw{"); for (int i=nelem-1; i>=0; i--) { printf("%d", A[i]); } printf("}\n"); return 0; }
実行結果
少し余計な部分がありますが、
一番下に出力した cpaw{...} の部分が Flag です。
program starts.
memory size all:288 / one:4
array elements: 72
before = {15, 1, 93, 52, 66, 31, 87, 0, 42, 77, 46, 24, 99, 10, 19, 36, 27, 4, 58, 76, 2, 81, 50, 102, 33, 94, 20, 14, 80, 82, 49, 41, 12, 143, 121, 7, 111, 100, 60, 55, 108, 34, 150, 103, 109, 130, 25, 54, 57, 159, 136, 110, 3, 167, 119, 72, 18, 151, 105, 171, 160, 144, 85, 201, 193, 188, 190, 146, 210, 211, 63, 207}
sorted list = {0, 1, 2, 3, 4, 7, 10, 12, 14, 15, 18, 19, 20, 24, 25, 27, 31, 33, 34, 36, 41, 42, 46, 49, 50, 52, 54, 55, 57, 58, 60, 63, 66, 72, 76, 77, 80, 81, 82, 85, 87, 93, 94, 99, 100, 102, 103, 105, 108, 109, 110, 111, 119, 121, 130, 136, 143, 144, 146, 150, 151, 159, 160, 167, 171, 188, 190, 193, 201, 207, 210, 211}
The flag is below:
cpaw{2112102072011931901881711671601591511501461441431361301211191111101091081051031021009994938785828180777672666360585755545250494642413634333127252420191815141210743210}
submit
なんとなくソートといえば、昇順に並べるイメージがあり、
そのまま文字列として繋げて出力してしまったため、cpaw{昇順} で提出してしまい、
一度 invalid answer をくらってしまいました。問題文はよく読みましょう、ですね (自戒)。
ということで、今回も提出完了です。
ここまでで、Level 1 の問題をなんとか完答することができました。
僕は割とこういった、キリの良いところ、でやめてしまう性分があるので、
なんとか Level 2 以上の問題についても、そして Level 1 で後回しにした知識の部分に関しても、
今後とも、きちんとフォローしていけたらな、と思っています (気持ちだけはある...)。
続きがあることを信じて。それでは。
