Алгоритм Python, чтобы найти индексы k наименьшего числа в несортированном массиве?

Question

Есть ли какой-нибудь алгоритм для поиска индексов k наименьших чисел в несортированном массиве в python? Я знаю, как этого можно добиться, используя numpy модуль, но я не ищу этого. Одно направление, которое сразу приходит мне в голову, - это алгоритмы сортировки. Допустим, у меня есть алгоритм сортировки массива в Python с использованием Bubble sort:

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

# Traverse through all array elements
for i in range(n):

    for j in range(0, 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]

Я не уверен, как изменить этот алгоритм на , просто вернуть индексы наименьшего числа k в массиве. Любая помощь с использованием алгоритма сортировки или выбора алгоритма, такого как quickselect, quicksort, будет оценена.

РЕДАКТИРОВАТЬ 1: скажем, массив:

a = [12, 11, 0, 35, 16, 17, 23, 21, 5]

Тогда он должен просто вернуть массив: index_of_least_k = [2,8,1]

для k = 3.

Если бы мне пришлось изменить алгоритм сортировки, скажем, пузырьковая сортировка, я понимаю, как это изменить, чтобы на этот раз поменять местами индексы, скажем:

def modified_bubbleSort(arr, index):
      n = len(arr)

      # Traverse through all array elements
      for i in range(n):

           for j in range(0, n-i-1):
                  # Swap if the element found is greater
                  # than the next element
                  if arr[j] > arr[j+1] :
                         index[j], index[j+1] = index[j+1], index[j]
      return index


array = [12, 11, 0, 35, 16, 17, 23, 21, 5]
index = [0, 1, 2, 3, 4, 5, 6, 7, 8]

indexOfAllsorted = modified_bubblesort(array, index)

В этом случае он возвращает меня:

indexOfAllsorted = [2,8,1,0,4,5,7,6]

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

index_of_least_k = [0, 0, 0]

в памяти для k = 3, а затем заполнить его по мере продвижения. Надеюсь, я дал понять.

EDIT2: я не ищу библиотеку или модули для этого в python.

Answer 1

Вы можете использовать heapq.nsmallest, чтобы получить n мельчайшие элементы из итерируемого.Так как же создать итерацию, которая измеряет значения входных данных, но возвращает их индексы?Одним из способов является использование функции enumerate для получения итерируемой пары (index, value), а затем использование ключевой функции для использования только значений.

from heapq import nsmallest
from operator import itemgetter

def indices_of_n_smallest(n, seq):
    smallest_with_indices = nsmallest(n, enumerate(seq), key=itemgetter(1))
    return [i for i, x in smallest_with_indices]

array = [12, 11, 0, 35, 16, 17, 23, 21, 5]
indices_of_n_smallest(3, array)
# [2, 8, 1]

Answer 2

Вот что такое пузырьковая сортировка.Каждый раз, когда внутренний цикл завершает итерацию, ровно один элемент находит свою правильную позицию.Ваш код, например, каждый раз находит i-й по величине элемент, поскольку он сортируется в порядке возрастания.Давайте перевернем этот> знак на <;теперь он будет находить i-й наименьший элемент каждый раз, когда завершается цикл j.Поэтому, если вы остановите сортировку, когда i = k, у вас будет k самых маленьких элементов. </p>

def modified_bubbleSort(arr, index, k):
  n = len(arr)
  ans = []

  for i in range(k):

       for j in range(0, n-i-1):
              # Swap if the element found is smaller
              # than the next element
              if arr[index[j]] < arr[index[j+1]] :
                     index[j], index[j+1] = index[j+1], index[j]
       ans.append(index[n-i-1])
  return ans