プロジェクトタイトル

42_push_swap

概要

限られた命令セットと最小限の移動数を使用して、スタック上のデータを並べ替えます。

プロジェクトの目的

42Tokyoの課題であり、また、
さまざまな並べ替えアルゴリズムを操作し、最適化されたデータ並べ替えに最適なソリューションを選択し、
限られた命令セットと最小限の移動数を使用して、スタック上のデータを並べ替えます。

チャレンジした点

この課題で難所は二つ。 双方向リストの使い方の理解。 最短での入れ替えアルゴリズムを模索。
この二つだと思います。

どちらも試行錯誤しながら、周りの人に聞きながら進めていきました。
特に双方向リストは頭だけで考えるのは難しく、複数のポインタ操作が出てくるので、紙に書きながら理解を深めました。

学んだこと, 使ったアルゴリズム

双方向リストについて学びを得ました。 双方向リストを使うことで、sa(スタックの一番上を一番下に持っていき、全体の階層を一つ上にあげる。ロケット鉛筆のような感じです)
のような操作が容易になります。
特定の操作のみが課題として許されていたので、それに沿う形で実装しました。

また、自分は『三分割法』というアルゴリズムを使いました。
まず、スタックを二つ（A, B）用意し、最初のスタックに与えられた全ての数を入れます。
次にスタックAを、全体を30%, 10%で分けそれを二重ループを使い、スタックBに送っていきます。 結果として、スタックBは谷のような形をとるので、スタックAに戻すときに、最大値を探すときに、上か下に固まっているので、
探すときに入れ替える回数が少なくなるのが利点です。

このようなアルゴリムの組み立て、実装を一からできたのは良かったです。

使用方法

• normal

#!/bin/bash
cd 42_push_swap
make
./push_swap "(任意の数字列)"

• 例

#!/bin/bash  
./push_swap "2 1 3"  
sa(このような出力が期待されます)

• ランダムな数のテスト
  テスター をダウンロード

42_push_swapの直下にダウンロードしてきたファイルを配置してください。

#!/bin/bash  
ARG=$(jot -r -s " " 100 -2147483648 2147483647); ./push_swap $ARG | ./checker_Mac $ARG

技術スタック

C言語