Pythonのバブルソートの複雑さ

Question

プログラミング初心者でPythonを学んでいます。私はインターネット上で2つのサイクルを使って多くのバブルの種類を見た。私はそれを理解しましたが、サイクルを使って自分自身で書きたいと思っていました。私は最終的にそれを書いて、それは動作します。私のコードには複雑さがあり、おそらく悪いです。何人かの人は、私がそれを変更すると "速い"と言いました。 たとえば、6のソートされていない数値を入力すると複雑さは25です。しかし、6つのソートされた数値（たとえば1,2,3,4,5,6）を入力すると、複雑さはまだ25です。 5、いいえ？私は条件でいくつかを追加しますが、didntの仕事で。

lst=[] 
number="" 
while number!="k": 
    number=input("Enter a nubmer (to end press K): ") 
    if number!="k": 
     number=int(number) 
     lst.append(number) 
print("Numbers before: ",lst,) 

repetition=len(lst)-1 
index=0 
complexity=0 
while repetition>0: 
    repetition=repetition-1 
    while index<=len(lst)-2: 
     complexity=complexity+1 
     if lst[index]>lst[index+1]: 
       hlp=lst[index] 
       lst[index]=lst[index+1] 
       lst[index+1]=hlp 
     index=index+1   
    index=0 

print("Numbers after: ",lst,) 
print("Complexity:",complexity,) 

私はそれをどこで変更するべきか教えていただけますか？ありがとうございました。

Answer 1

バブルソルトアルゴリズムの複雑さは、それを実装するために選択されたプログラミング言語に関係なく、最悪の場合、常にO(N^2)になります。

Answer 2

バブルソートは常に最初のリストの順序に関係なく、常に各要素ペアを通過するため、N^2ランタイムです。複雑さはソートしているリストの順序にかかわらずコードと同じでなければならないので、複雑さの出力はその意味で正しいです。複雑さを改善するには、別のソートアルゴリズムが必要です。