挿入ソートを理解する: 質問主導のアプローチ

このブログ投稿では、挿入ソート アルゴリズムの基礎を理解するために質問主導のアプローチを採用します。私は、これから学ぶ挿入アルゴリズムやその他のアルゴリズムを理解するためのより良い方法を見つけようとしていたときに、このアプローチを思いつきました。私は、これから学習するアルゴリズムのすべてではないにしても、ほとんどに適用できる戦略を構築したいと考えていました。このことを考えているときに、第一原理思考を使用する必要があるかもしれないと確信しました

第一原理思考に触発されたこのアプローチでは、最初の理解が曖昧であっても明確であっても、まずアルゴリズムを把握しようとします。次に、アルゴリズムを構成する小さな概念や仕組みを特定します。これらのメカニズムや小さな概念に関する質問を作成することによって。私たちは基本的に、独自に形成した質問を解決することに重点を置き、アルゴリズムの動作を小さな異なる視点から理解しようとしています。

作成した回答は、最初は実際のアルゴリズムで使用される構文に似ている場合もあれば、似ていない場合もあります。目標は、構文が近いかどうかに関係なく、質問に自分で答えることです。明確に理解したら、アルゴリズムの実際の実装と同様に、構文を使用するために回答を変換、マージできます。このプロセスにより、コードの代替形式を探索し、特定の構文が使用されている理由を把握し、エッジケースに自分自身でより適切な方法で対処できるようになると信じています。

この方法により、コードの各行の背後にある理論と推論が確実に理解され、実装プロセスがより直感的で意味のあるものになると思います。次の質問と私が経験した思考プロセスは、挿入ソートをより深く理解し、効果的にコーディングできるようにするのに役立ちました。

あなたにとって、質問は異なるかもしれません。より多くの場合もあれば、より少ない場合もあれば、まったく異なる場合もあります。これはリバース エンジニアリングに似ていると言う人もいるかもしれませんが、何と呼ぶにせよ、この方法により挿入ソート アルゴリズムを完全に理解することができました。他のアルゴリズムでも同じことができることを願っています。さあ、飛び込みましょう!

挿入ソートの実装

これは、最終的に挿入並べ替え用に実装するコードの形式です。

def insertion_sort(values):

    for new_value_index in range(1,len(values)):

        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1

        values[index+1] = new_value

質問

ソートされたリストを指定して、while ループを使用して値を右から左に出力します。

values = [4,8,12,16,20,24,30]
# given a sorted list, using while loop, print values from right to left.

index = len(values)-1
while index>=0:
    print(values[index],end = " ")
    index-=1

ソートされたリストと新しい値が与えられた場合、リストのソートを維持するために新しい値が挿入されるインデックスを見つけます。

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# using while loop, if traversing from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value: break
    index-=1

print(values,new_value,index)

並べ替えられたリストと新しい値が指定された場合、並べ替えられたままになるように新しい値をリストに挿入します。

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# if traversal from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value:break
    index-=1

values = values[:index+1] + [new_value] + values[index+1:]
print(values)

ソートされたリストに新しい値を追加し、その新しい値を指定されたインデックス位置に移動します。

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

given_index = 3

# above given

n = len(values)-1

index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

print(values)

values[given_index+1] = new_value

print(values)

並べ替えられたリストに新しい値を追加して、リストを並べ替えます。

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

print(values)

### given a sorted list, then appended with new value, sort the list
####

n = len(values)-1
new_value = values[-1]

# find the index at which the value is to be inserted
# right to left
index = n-1
while index>=0:
    if values[index]<new_value:break
    index-=1
given_index = index 
print("given_index : "  , given_index)

# move the values forward by one step until we reach the given index
index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

values[index+1] = new_value

print(values)

並べ替えられたリストに新しい値を追加して、リストを並べ替えます。

values = [4, 8, 12, 16, 20, 24, 30]

new_values = [14,32]

values += new_values

print(values)

# given a sorted list, then appended with two new value(s), sort the list

n = len(values)-1

new_value_start_index = n - 1

print(new_value_start_index, values[new_value_start_index])

for new_value_index in range(new_value_start_index,len(values)):

    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value: break
        values[index+1] = values[index]
        index-=1

    values[index+1] = new_value

print(values)

与えられたリストを並べ替えます。

import random

values = random.sample(range(10,90), k = 10)

values

print(values)

for new_value_index in range(1,len(values)):
    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value:break
        values[index+1] = values[index]
        index-=1
    values[index+1] = new_value

print(values)

挿入ソートの実装

def insertion_sort(values):
    for new_value_index in range(1,len(values)):
        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1
        values[index+1] = new_value

追加リソース

最初はアルゴリズムをよりよく理解するために包括的な一連の質問に取り組みましたが、上記の一連の質問は挿入ソートをよりよく理解するために重要であると考えられます。私が取り組んだすべての質問を含めると、投稿はかなり長くなるでしょう。

すべての質問をご覧になりたい方のために、質問の完全なセットと私自身の回答を含む Jupyter Notebook を作成しました。これにより、Insertion Sort の実装を完全に理解することができました。

さらに詳しく知りたい場合は、ノートブックをチェックすることをお勧めします。

修正や提案は大歓迎です。

以上が挿入ソートを理解する: 質問主導のアプローチの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。