バブルソートよりも効率的なソートアルゴリズム

Question

バブルソートを使用してリストをソートするアルゴリズムを記述しました。これはリストをソートする最も効率的な方法ですか？
そうでない場合、なぜですか？
なぜ効率が悪く、選択肢は何ですか？

def BubbleSort(List): 
    for i in range(len(List)-1): 
      for Number in range(len(List)-1): 
       if List[Number] > List[Number+1]: 
        List[Number], List[Number+1] = List[Number+1], List[Number] 

print(BubbleSort([5,2,1,4,3]) 

ありがとう！

Answer 1

上記のアルゴリズムでは、配列のlengthが5の場合は、if statement25回を実行します。一般的に、nのサイズのリストがある場合は、の操作はfor loopとswappingを除いて行われます。

サイズ10^6のリストについては、10^12操作以上です。 CまたはC++ do約10^9操作/秒あなたのこのコードは30分以上かかる10^3秒かかるでしょう。だから非常に非効率的です。

より速いので、bubble sortの代わりに使用できるソートアルゴリズムがあります。

• Merge Sort
• Quick Sort
• Heap Sort

他の技術の多くはそこにもあるが、これらは使用される最も一般的です。

これらのアルゴリズムを実装する必要はありません。最も効率的なアルゴリズムの1つが、ほとんどの言語の標準ライブラリ（C〜Rust）で既に実装されているためです。その実装を使用することもできますし、必要に応じて独自のcomparator関数を渡すこともできます。