Lab3：ソート

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

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

〆切

2021年12月31日金曜日11:59 PM (東部標準時) までに提出してください。

背景

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

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

始め方

  1. GitHubアカウントを使用してide.cs50.ioにログインします。
  2. ターミナルウィンドウでwget https://cdn.cs50.net/2020/fall/labs/3/lab3.zipを実行し、実習の配布コードのZipファイルをダウンロードします。
  3. ターミナルウィンドウでunzip lab3.zipを実行して、そのZipファイルを解凍します。
  4. ターミナルウィンドウで、cd lab3を実行してディレクトリをlab3ディレクトリに変更します。

インストラクション

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

  • sort1、sort2、およびsort3はバイナリファイルであるため、それぞれのCソースコードを表示することはできません。どのソートがどのアルゴリズムを実装するかを評価するには、様々な値のリストでソートを実行します。
  • 複数の.txtファイルが提供されます。これらのファイルには、反転、シャッフル、またはソートされたn行の値が含まれます。
    • たとえば、reversed10000.txtには10000から逆順の10000行の数値が含まれ、random100000.txtにはランダムな順序の10万行の数値が含まれます。
  • テキストファイルに対してソートを実行するには、ターミナルで./[program_name] [text_file.txt]を実行します。
    • たとえば、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/2021/x/sort

提出方法

次のコマンドを実行し、GitHubのユーザー名とパスワードを入力してログインします。セキュリティのため、パスワードには実際の文字ではなくアスタリスク (*) が表示されます。

submit50 cs50/labs/2021/x/sort