Есть ли название для этого вида и какие данные это эффективно для сортировки?

Question

Я пытался написать Bubble вроде по памяти в поезде на работу этим утром, но вместо этого придумал.

Есть ли название для этого типа сортировки?

def not_bubble_sort(arr):
    length = len(arr)
    while True:
        is_sorted = True
        for i in range(length - 1):
            if arr[i] > arr[i + 1]:
                is_sorted = False
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        if is_sorted:
            break

    return arr

Я ожидал, что это будет крайне неэффективно, по некоторым данным. Но для других случайно сгенерированных списков это было очень быстро, может кто-нибудь объяснить, почему это так. Есть ли способ использовать это? Или я где-то допустил ошибку.

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

Тест запускает сортировку по сгенерированному списку из n randint целых чисел.

N = 5000
------
|  min          |  avg          |  max          |  func             |  name             |
|---------------|---------------|---------------|-------------------|-------------------|
|  0.000463724  |  0.034745610  |  3.425408840  |  not_bubble_sort  |  sarcoma          |
|  1.159517288  |  1.212791989  |  1.768434763  |  bubble_sort      |  geeks_for_geeks  |

Пример Geeks for Geeks Bubble Сортировка:

def bubble_sort(arr):
    n = len(arr)

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

    return arr

https://github.com/sarcoma/algorithms-python/blob/master/algorithms/sort/bubble_sort.py

Answer 1

Это просто пузырьковая сортировка, но с ранним выходом.

В «реальной» пузырьковой сортировке вы перебираете массив length-1 раз, независимо от того, как выглядят данные, но здесь, если на каком-то более раннем этапе данные сортируются, вы break.

И неэффективность происходит из-за того, что ваш алгоритм имеет сложность "O (n ^ 2)" вместо "O (1/2 * n ^ 2)" * (из-за этого for i in range(length - 1): вместо этого for j in range(0, n - i - 1):)

* не очень большая буква O, но это доказывает смысл