Lab3

この Lab では1~2人のクラスメートと協力することは問題ありませんが、そのグループのすべての受講生が等しく実習に貢献することが求められます。

3つのソートプログラムを分析して、使用するアルゴリズムを決定します

背景

レッスンでは、選択ソート、バブルソート、マージソートなど、一連の数値をソートするためのアルゴリズムをいくつか紹介しました。

  • 選択ソート(Selection sort)は、リストのソートされていない部分を繰り返し処理し、毎回最小の要素を選択して、それを正しい位置に移動します。
  • バブルソート(Bubble sort)では、隣接する値のペアが一度に1つずつ比較され、順序が正しくない場合はスワップされます。これは、リストがソートされるまで続きます。
  • マージソート(Merge sort)は、リストを繰り返し2つに分割し、小さいリストを正しい順序で大きいリストにマージします。

入門

VS Codeを開きます。

ターミナルウィンドウ内をクリックすることから始めて、それからcdを実行します。
その後プロンプトは次のようになっていることがわかります。

$

ターミナルウィンドウの内側をクリックし、次のように入力します。

wget https://cdn.cs50.net/2021/fall/labs/3/sort.zip

その後にEnterを押すと、sort.zipというZIPがあなたのCodespaceにダウンロードされます。wgetと次のURLの間にあるスペースや、その他の文字を見落とさないように注意してください。

次に

unzip sort.zip

を実行して、sortというフォルダを作成します。
ZIPファイルは不要になったため、

rm sort.zip

を実行し、プロンプトで “y “に続いてEnterで応答すると、ダウンロードしたZIPファイルが削除されます。

次に

cd sort

の後にEnterを押して、そのディレクトリに移動する（つまり、開く）。これでプロンプトは以下のようになります。

sort/ $

すべて成功した場合は、次のように実行します。

ls

実行可能なプログラムsort1、sort2、sort3とともに、.txtファイルが表示されるはずです。

問題が発生した場合は、同じ手順をもう一度実行して、どこが間違っていたかを判断できるかどうかを確認してください。

インストラクション

コンパイル済みのCプログラムとして、sort1、sort2、sort3が提供されています。これらのプログラムはそれぞれ、選択ソート、バブルソート、マージソート (必ずしもこの順番ではありません！) という異なるソートアルゴリズムを実装しています。各ファイルで使用するソートアルゴリズムを決定する必要があります。

  • sort1、sort2、およびsort3はバイナリファイルであるため、それぞれのCソースコードを表示することはできません。どのソートがどのアルゴリズムを実装するかを評価するには、様々な値のリストでソートを実行します。
  • 複数の.txtファイルが提供されます。これらのファイルには、反転、シャッフル、またはソートされたn行の値が含まれます。
    • たとえば、reversed10000.txtには10000から逆順の10000行の数値が含まれ、random100000.txtにはランダムな順序の10万行の数値が含まれます。
  • テキストファイルに対してソートを実行するには、ターミナルで./[program_name] [text_file.txt]を実行します。cd を使ってソートディレクトリに移動していることを確認してください。
    • たとえば、reversed10000.txtをsort1でソートするには、run ./sort1 reversed10000.txtを実行します。
  • ソートの時間を計ると便利です。これを行うには、time ./[sort_file] [text_file.txt]を使用します。
    • たとえば、time ./sort1 reversed10000.txtを使用して、1万個の逆順の数に対してsort1 を実行します。ターミナルの出力の最後で、プログラムの実行中に実際に経過した時間をrealで確認できます。
  • 回答はanswers.txtに記録し、TODOと書かれた空欄にプログラムの説明を記入します。

ウォークスルー

ヒント

  • .txtファイルにさまざまな種類があるため、どの並べ替えを行うかを決定するのに役立ちます。すでにソートされたリストを使用して、各アルゴリズムがどのように実行されるかを検討します。逆順のリストはどうですか？シャッフルされたリストは？各タイプのより小さなリストを作成して、各ソートプロセスをウォークスルーすると便利です。

解決方法がわかりませんか？

コードのテスト方法

以下を実行して、check50であなたの回答が正しいかどうかを評価してください。また、ここではcheck50がチェックしない説明も必ず記入してください!

check50 cs50/labs/2022/x/sort

提出方法

ターミナルで以下を実行し、提出してください。

submit50 cs50/labs/2022/x/sort