как называется этот алгоритм сортировки? это пузырьковая сортировка? самая легкая сортировка?

Question

как называется этот сорт? это как пузырьковая сортировка, но ее легко написать, но сложнее с точки зрения сложности. коды находятся на языке python.

def sort(arr): 
    n = len(arr) 
    for i in range(n):
        for j in range(n):
            if arr[i] < arr[j] : 
                arr[j], arr[i] = arr[i], arr[j] 

, но пузырьковая сортировка выглядит так:

def bubbleSort(arr): 
    n = len(arr) 
  
    # Traverse through all array elements 
    for i in range(n): 
  
        # Last i elements are already in place 
        for j in range(0, n-i-1): 
  
            # traverse the array from 0 to n-i-1 
            # Swap if the element found is greater 
            # than the next element 
            if arr[j] > arr[j+1] : 
                arr[j], arr[j+1] = arr[j+1], arr[j]

Answer 1

Это не сортировка по выбору и не пузырьковая сортировка, а ненужная плохая сортировка. Все они, ваша сортировка, сортировка выбора и пузырьковая сортировка имеют одинаковую сложность, O (n ^ 2).

Ваша сортировка проходит по массиву в двух циклах без учета того, достиг ли элемент своего должного место (как при сортировке по выбору) или если элемент занял место относительно следующего (как при пузырьковой сортировке). Дополнительный код в пузырьковой и выборочной сортировке делает их намного лучше, чем у вас.

Сравните сами:

def sort(arr):
    print(arr)
    n = len(arr) 
    for i in range(n):
        for j in range(n):
            if arr[i] < arr[j] :
                arr[j], arr[i] = arr[i], arr[j]
                print(arr)

def selectionsort(arr):
    print(arr)
    n = len(arr)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
        print(arr)

def bubblesort(arr): 
    print(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]
                print(arr)

print("sort:")
sort([4,6,3,2,7,1,8,5])
print("selectionsort:")
selectionsort([4,6,3,2,7,1,8,5])
print("bubblesort:")
bubblesort([4,6,3,2,7,1,8,5])

с результатами:

sort:
[4, 6, 3, 2, 7, 1, 8, 5]
[6, 4, 3, 2, 7, 1, 8, 5]
[7, 4, 3, 2, 6, 1, 8, 5]
[8, 4, 3, 2, 6, 1, 7, 5]
[4, 8, 3, 2, 6, 1, 7, 5]
[3, 8, 4, 2, 6, 1, 7, 5]
[3, 4, 8, 2, 6, 1, 7, 5]
[2, 4, 8, 3, 6, 1, 7, 5]
[2, 3, 8, 4, 6, 1, 7, 5]
[2, 3, 4, 8, 6, 1, 7, 5]
[2, 3, 4, 6, 8, 1, 7, 5]
[1, 3, 4, 6, 8, 2, 7, 5]
[1, 2, 4, 6, 8, 3, 7, 5]
[1, 2, 3, 6, 8, 4, 7, 5]
[1, 2, 3, 4, 8, 6, 7, 5]
[1, 2, 3, 4, 6, 8, 7, 5]
[1, 2, 3, 4, 6, 7, 8, 5]
[1, 2, 3, 4, 5, 7, 8, 6]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
selectionsort:
[4, 6, 3, 2, 7, 1, 8, 5]
[1, 6, 3, 2, 7, 4, 8, 5]
[1, 2, 3, 6, 7, 4, 8, 5]
[1, 2, 3, 6, 7, 4, 8, 5]
[1, 2, 3, 4, 7, 6, 8, 5]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
bubblesort:
[4, 6, 3, 2, 7, 1, 8, 5]
[4, 3, 6, 2, 7, 1, 8, 5]
[4, 3, 2, 6, 7, 1, 8, 5]
[4, 3, 2, 6, 1, 7, 8, 5]
[4, 3, 2, 6, 1, 7, 5, 8]
[3, 4, 2, 6, 1, 7, 5, 8]
[3, 2, 4, 6, 1, 7, 5, 8]
[3, 2, 4, 1, 6, 7, 5, 8]
[3, 2, 4, 1, 6, 5, 7, 8]
[2, 3, 4, 1, 6, 5, 7, 8]
[2, 3, 1, 4, 6, 5, 7, 8]
[2, 3, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

Это не ' t имеет большое значение для небольших массивов, но для больших массивов это имеет большое значение (но есть и другие методы).