挿入ソートアルゴリズム:どのコードがその構造で効率的で、どうやって来るのか

2020-08-01 python python-3.x algorithm sorting insertion-sort

挿入ソートアルゴリズムのソースコードを2つ作りました。

def insertsort(iterable) :
    
    for current in range(len(iterable)) : # 'current' is the index of the element being sorted

        compare, n = 0,0 # Initializes 'compare' and 'n' which is used in for-loop in each current for-loop
        current_value = iterable[current] # Saves the element being sorted since the corresponding space will be assigned by the leading value
        
        for compare in range(0,current) : # Compares the element from [0] to the element right ahead of [current]            
            if iterable[compare] > iterable[current] : # Finds where to insert 'current_value,' stored value of [current]

                for n in range(current,compare,-1) : # Translate the values to one space to make the space where 'current_value' will be put empty
                    iterable[n] = iterable[n-1]
                    
                iterable[compare] = current_value # Insert the saved value of [current] to the right place
                
    return(iterable)

最初のものは私がガイドなしで自分で作ったものです。

def insertsort(iterable) :
    for current in range(1,len(iterable)) : # iterable[0] is consdiered as resorted in the beginning
        current_value = iterable[current] # saving current value
        compare = current
        while 0 < compare and iterable[compare-1] > current_value : # finding out where to put the sorted current value
            iterable[compare] = iterable[compare-1] # this line in the while loop moves the elements not sorted
            compare -= 1 

        iterable[compare] = current_value # put current value into the right place that the while loop found out


    return(iterable)

2つ目は、私がいくつかのWebページを見て作成したものです。

2つを比較すると、インターネットからの2番目は、私が作成したものより短いことがわかりました。

2番目は、10時間の平均実行時間による一見効率的なパフォーマンスも示し、10000の連続する要素をソートしました(データ= [範囲内のi(10000、0、-1))]

すべてを並べ替えるのに約16秒かかりましたが、約0.4秒速くなりました。

ただし、100,000の連続する要素(data = [i for i in range(100000、0、-1)])でテストすると、最初の要素(私が作成したもの)は2番目の要素よりも高速でした。

最初のものは約1700秒で、2番目のものより200秒高速です。

これが私の質問です。

  1. 各コードの時間の複雑さはどれくらいですか?確かではありませんが、両方ともn ^ 2であると思います。
  2. 私が作成したものの方がパフォーマンスが良いように見えるのはなぜですか? 2番目のループでforループとifステートメントをwhileループに作成しましたが、それを遅くすると思います。

念のため、使った計時方法をつけておきます。 https://stackoverflow.com/a/1557584を参照しました

Answers

Related