バブルソートを実装する正しい方法ですか？

Question

バブルソートを実装する正しい方法ですか？ ソートされたリストが表示されますが、その方法が正しいかどうかは疑問です。

# Input unsorted list 
size_lis = int(input("enter the size of the list")) 
size = 0 
list1 = list() 

while (size < size_lis): 
    element = int(input("enter the element")) 
    list1.append(element) 
    size += 1 

# Sort 
for i in range(0, len(list1)): 
    for j in range(0, len(list1)-1): 
     if list1[j] > list1[j+1]: 
      list1[j],list1[j+1] = list1[j+1],list1[j] 

print(list1) 

Answer 1

これは、バブルソートアルゴリズムの正しい実装です。逆の順序（ - 最も効率的な方法でリストを反転させるための操作[::-1]）にrange(len(arr))を反復処理

def bubble_sort(arr): 
    for i in range(len(arr))[::-1]: 
     for j in range(1, i + 1): 
      if arr[j - 1] > arr[j]: 
       arr[j], arr[j-1] = arr[j-1], arr[j] 

まずループ：しかし、あなたは、実装のこの種を使用して、余分なループを防止することができます。このループの最初の反復の後、リストの最大要素がリストの最後に配置されます。そして、2番目のループは残りの要素だけを反復する必要があります。

私はあなたの要素（bubble_sort_2）と鉱山（bubble_sort）の実装を、1000要素の2つの同一の配列を使ってテストしました。 bubble_sortがbubble_sort_2よりも高速です、あなたが見ることができるように

ncalls tottime percall cumtime percall filename:lineno(function) 
    1 0.215 0.215 0.215 0.215 bs.py:22(bubble_sort_2) 
    1 0.128 0.128 0.128 0.128 bs.py:16(bubble_sort) 

：ここ は（cProfileを使用して）結果です。

Answer 2

バブルソートでは、最大の要素がステップごとにリストの最後に移動されます。したがって、最初のパスの後に、この1つの要素が最終位置にあります。 2番目のパスは残りのN-1個の要素のみをソートする必要があります。

投稿コードでは、このような内側の円を調整してください。それはCPU時間の約50％を節約します。

n = len(lst) 
for i in range(n): 
    for j in range(n-i-1): 
     if lst[j] > lst[j+1]: 
      lst[j], lst[j+1] = lst[j+1],lst[j]