Алгоритмы сортировки более эффективны, чем сортировка пузырьков

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, он наверняка сделает n^2 операций, за исключением for loop и swapping.

Список 10^6, это будет 10^12 операций по крайней мере. C или C++ делать около 10^9 операций в секунду. Таким образом, этот ваш код займет 10^3 секунд, что составляет более получаса. Так что это очень неэффективно.

Есть лучшие алгоритмы сортировки, которые вы можете использовать вместо bubble sort, поскольку они быстрее этого.

• Merge Sort
• Quick Sort
• Heap Sort

Много других методов также есть, но они являются наиболее распространенными используются.

Кроме того, вам не нужно реализовывать эти алгоритмы, поскольку один из наиболее эффективных из них уже реализован в стандартной библиотеке в основном на каждом языке от C до Rust. Вы можете просто использовать эту реализацию и даже передать свою собственную функцию comparator, если хотите.