Удалить наименьшее значение из массива после добавления в новый массив

Question

Я использую функцию сортировки выборки в Python, которая работает с пустыми массивами вместо списков (поэтому я не могу использовать .pop для этого, я не думаю).

Функция:

def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr) 
        newArr.append((smallest)) 
        arr = arr[(arr > smallest)]
    return newArr

Я хочу, чтобы "arr = arr [(arr> smalllest)], который явно не работает, чтобы удалить наименьшее значение (или значение, добавленное к newArr, т.е. то же значение) из переданногомассив так же, как .pop будет делать со списком.

Я пробовал что-то вроде этого:

a = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9])
index = [2, 3, 6]

new_a = np.delete(a, index)

Но не смог заставить его работать. В концедня мне нужно получить что-то в формате:

arr = randint(0,10,20)

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

Спасибоза любую помощь

Answer 1

Вы можете попробовать:

arr = arr[ arr != np.min(a)]

Таким образом вы возьмете из arr все элементы, кроме самого маленького, и переназначите их на arr.

Answer 2

Ваш алгоритм почти правильный.Действительно, это работает, если в arr:

import numpy as np

def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr) 
        newArr.append((smallest)) 
        arr = arr[(arr > smallest)]
    return newArr

findSmallest = np.min

# no duplicate values
auniq = np.random.choice(np.arange(20), (10,), replace=False)

print(auniq)
print(selectionSort(auniq))

нет повторяющихся значений. Пример выполнения:

[ 0  1  7  4 10 14 13 16  9 12]
[0, 1, 4, 7, 9, 10, 12, 13, 14, 16]

При наличии дубликатов происходит сбой, поскольку при удалении минимума с дубликатамидубликаты также будут удалены, и это нарушает логику цикла.

# duplicate values
adupl = np.random.randint(0, 9, (10,))

print(adupl)
# next line would crash
#print(selectionSort(adupl))

Одно исправление - удалить только одну копию дубликатов.Это можно сделать, например, используя argmin, который возвращает индекс минимума / один, а не его значение.

def selectionSort2(arr):
    arr = np.array(arr)
    sorted = np.empty_like(arr)
    for i in range(len(sorted)):
        j = arr.argmin()
        sorted[i] = arr[j]
        arr = np.delete(arr, j)
    return sorted

print(selectionSort2(adupl))

Это работает, но ужасно неэффективно, поскольку np.delete более или менее O (n).Дешевле поменять местами минимальный элемент с граничным элементом, а затем обрезать его:

def selectionSort3(arr):
    arr = np.array(arr)
    sorted = np.empty_like(arr)
    for i in range(len(sorted)):
        j = arr[i:].argmin()
        sorted[i] = arr[i + j]
        arr[i], arr[i + j] = arr[i + j], arr[i]
    return sorted

print(selectionSort3(adupl))

Глядя на selectionSort3, мы видим, что отдельный вывод sorted на самом деле не нужен, потому что arr уже отсортировано на месте:

def selectionSort4(arr):
    arr = np.array(arr)
    for i in range(len(arr)):
        j = arr[i:].argmin()
        arr[i], arr[i + j] = arr[i + j], arr[i]
    return arr

print(selectionSort4(adupl))

Пример вывода (adupl и вывод selectionSort2-4):

[0 4 3 8 8 4 5 0 4 2]
[0 0 2 3 4 4 4 5 8 8]
[0 0 2 3 4 4 4 5 8 8]
[0 0 2 3 4 4 4 5 8 8]

Answer 3

Попробуйте

arr = arr[np.where(arr > smallest)]