並べ替えはプログラマーにとって必須のコースであり、新しい言語をテストする最良の方法でもあります。
その理由は非常に現実的です。並べ替えアルゴリズムの後は、リスト、ループ、関数、比較演算を含む 4 つすべてが使用されます。これら 4 つは、日常のコーディングで最も頻繁に登場するインフラストラクチャです。それらを分類して順番に書けば、この言語はマスターされます。
最初の 3 つの記事では、Hello World、身体検査ツールの構成、およびパフォーマンス テストについて書きました。この記事では姿勢を変えてアルゴリズムを使って練習します。
まずは既成の答えを見てみましょう
CatBase マニュアルに記載されている組み込み関数名には、 sorted そして reversed。並べ替えに関しては、言語自体がすぐに答えを出してくれます。
def main(args: list[str]) {
nums: list[int] = [5, 3, 8, 1, 9, 2]
print("原始: ", nums, "\n")
print("排序后: ", sorted(nums), "\n")
}
実用的な提案: 運用環境では、組み込みの sorted()。その最下層は成熟したソート実装であり、手動で作成できるどのバージョンよりも高速で、手動で作成できるどのバージョンよりも間違いが起こりにくくなっています。
では、なぜ手書きで書くのでしょうか？理由は 3 つあります。面接にはテストが必要であり、原則を理解し、実践が真実でなければなりません。バブルソートを手書きすることで、「比較」や「交換」についての理解がさらに深まります。このレベルは、フレームワークのソース コードを確認するときに役立ちます。
以下の 3 つのアルゴリズムはすべてマニュアルで確認された構文を使用して記述されています。
バブルソート
原理は、隣接する 2 つの数値を繰り返し比較し、大きい方の数値を元に戻し、各ラウンドで現在の最大の数値をキューの最後に送信することです。
def bubble_sort(nums: list[int]) -> list[int] {
n: int = len(nums)
i: int = 0
while i < n {
j: int = 0
while j < n - 1 - i {
if nums[j] > nums[j + 1] {
tmp: int = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = tmp
}
j = j + 1
}
i = i + 1
}
return nums
}
コードで使用されている構文については、マニュアルを 1 つずつ読んでください。while サイクル、if 比較する、len()リスト インデックスの読み取りと書き込み、整数の加算と減算はすべて公式の例でサポートされています。
知らせ n - 1 - i この詳細。各ラウンド後、チームの終了時に最大値が固定されるため、内側のループの上限はラウンドごとに 1 ずつ減ります。この最適化についての記述を少なくすると、結果は同じになりますが、無駄な比較が増えるだけです。
選択ソート
原則は別のアイデアに変更されます。各ラウンドで、ソートされていない区間で最小値が検出され、区間の先頭に直接配置されます。
def selection_sort(nums: list[int]) -> list[int] {
n: int = len(nums)
i: int = 0
while i < n {
min_idx: int = i
j: int = i + 1
while j < n {
if nums[j] < nums[min_idx] {
min_idx = j
}
j = j + 1
}
if min_idx > i {
tmp: int = nums[i]
nums[i] = nums[min_idx]
nums[min_idx] = tmp
}
i = i + 1
}
return nums
}
これは、バブル ソートによって実行される交換の数とは桁違いです。バブリングはラウンドごとに変更できますが、選択の並べ替えはラウンドごとに最大 1 回変更できます。データ転送コストが高いシナリオでは、その差はかなり大きくなります。
ちなみに、書き方にはトレードオフがあります。「最小値が現在位置かどうか」を判断する場合は、ここを使用します min_idx > i使い物にならない !=。なぜなら min_idx から i 始めるとどんどん大きくなっていきます。 2 つが等しい場合は、置換が行われていないことを意味します。 1つ > それで十分です。
挿入ソート
この原理は、人がトランプを並べる方法に最も近いものです。左手が並べられる部分であり、毎回新しいカードが正しい場所に挿入されます。
def insertion_sort(nums: list[int]) -> list[int] {
n: int = len(nums)
i: int = 1
while i < n {
key: int = nums[i]
j: int = i - 1
while j >= 0 and nums[j] > key {
nums[j + 1] = nums[j]
j = j - 1
}
nums[j + 1] = key
i = i + 1
}
return nums
}
3 つのアルゴリズムの中で、「データが基本的に順序付けされている」場合に良好なパフォーマンスを発揮するのは、挿入ソートだけです。ほぼ順序付けされたデータに対して実行すると、時間計算量は O(n) に近くなります。これが、多くの成熟したソート実装が、データ量が少なくなった後に挿入ソートに切り替える理由です。
一緒に走る
3 回書くよりも 1 回テストする方が良いです。 4 つのオプションを同じスクランブルされたリストに入れて、結果が一貫しているかどうかを確認します。
def bubble_sort(nums: list[int]) -> list[int] {
n: int = len(nums)
i: int = 0
while i < n {
j: int = 0
while j < n - 1 - i {
if nums[j] > nums[j + 1] {
tmp: int = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = tmp
}
j = j + 1
}
i = i + 1
}
return nums
}
def selection_sort(nums: list[int]) -> list[int] {
n: int = len(nums)
i: int = 0
while i < n {
min_idx: int = i
j: int = i + 1
while j < n {
if nums[j] < nums[min_idx] {
min_idx = j
}
j = j + 1
}
if min_idx > i {
tmp: int = nums[i]
nums[i] = nums[min_idx]
nums[min_idx] = tmp
}
i = i + 1
}
return nums
}
def insertion_sort(nums: list[int]) -> list[int] {
n: int = len(nums)
i: int = 1
while i < n {
key: int = nums[i]
j: int = i - 1
while j >= 0 and nums[j] > key {
nums[j + 1] = nums[j]
j = j - 1
}
nums[j + 1] = key
i = i + 1
}
return nums
}
def main(args: list[str]) {
base: list[int] = [5, 3, 8, 1, 9, 2, 7, 4, 6]
l1: list[int] = [5, 3, 8, 1, 9, 2, 7, 4, 6]
l2: list[int] = [5, 3, 8, 1, 9, 2, 7, 4, 6]
l3: list[int] = [5, 3, 8, 1, 9, 2, 7, 4, 6]
print("原始数据 : ", base, "\n")
print("内置 sorted: ", sorted(base), "\n")
print("冒泡排序 : ", bubble_sort(l1), "\n")
print("选择排序 : ", selection_sort(l2), "\n")
print("插入排序 : ", insertion_sort(l3), "\n")
}
コンパイルして実行します。
./bin/catbasecc sort.cat
./sort
4 つの行の並べ替え結果はまったく同じになるはずです。これは、アルゴリズムの正しさを検証する最も簡単な方法です。信頼できる実装で答えを確認します。
複雑さの比較
| アルゴリズム | 平均時間 | 最悪の時期 | 余分なスペース | 安定性 |
|---|---|---|---|---|
| バブルソート | O(n²) | O(n²) | ○(1) | 安定させる |
| 選択ソート | O(n²) | O(n²) | ○(1) | 不安定な |
| 挿入ソート | O(n²) | O(n²) | ○(1) | 安定させる |
| 組み込みのソート | O(n log n) | O(n log n) | の上） | 安定させる |
3 つの手書きバージョンの時間計算量は O(n²) です。データ量が数千に達すると、O(n log n) の差が肉眼で見えるようになります。つまり、手書きは理解のためのものであり、雇用のためのものではありません。
真実の言葉をいくつか
この記事には、ローカルで確認する必要がある場所が 2 か所あります。まずはそれらについてお話します。
まず、マニュアルには変数インデックスの割り当てとネストされたループに関する公式の例がありません。定数インデックスの割り当て nums[0] = 10 および変数インデックスの読み取り args[i] 例があり、その 2 つが組み合わされています nums[j] = x この記事ではそれを非常に密に使用していますが、確かにマニュアルには書かれていません。これは、テキスト全体の中で確認する必要がある唯一のポイントです。
次に、マニュアルには再帰的な例がないため、クイック ソートとマージ ソートは含まれていません。公式ドキュメントで再帰が確認されたら、次の記事に追記する予定です。
加えて sorted() マニュアルに記載されているのは組み込み関数名だけであり、署名は詳しく書かれていません。具体的な使用方法はローカルのバージョンによって異なります。
バージョンはまだ 0.6 であり、標準ライブラリの第 7 章はまだ完了していません。機能しないコードに遭遇した場合、公式 WeChat グループにエラー レポートを投げることは、ドキュメントへの記入を助けるとみなされる可能性があります。
最後に書きます
手書きの仕分けは驚くほどコスト効率が高くなります。 3 つのアルゴリズムを合計すると 80 行未満になり、リスト、ループ、関数、比較演算について完全に理解できるようになります。
初めてバブルソートを書いたときに誰から学んだかをまだ覚えていますか?コメントセクションでチャットしてください。
※参考元：CatBase公式サイトcatbase-lang.com、GitHubウェアハウスDoRobotAi/catbase-lang README、doc/catbase.md。複雑さの表は、アルゴリズムの一般的な結論です。
