Функция partition

Функция partition выполняет частичное упорядочивание элементов массива. Она гарантирует, что элемент с индексом kth находится на той позиции, которую он бы занимал в полностью отсортированном массиве. При этом все элементы слева от него меньше или равны, а все элементы справа - больше или равны этому значению. Первым параметром функция принимает массив, вторым - индекс или список индексов, которые должны оказаться на своих местах.

Синтаксис

np.partition(a, kth, [axis], [kind], [order])

Параметры функции:

a - входной массив, который необходимо частично упорядочить
kth - индекс или список индексов, которые должны оказаться на своих местах
axis - ось, вдоль которой производится упорядочивание (по умолчанию -1)
kind - алгоритм сортировки ('introselect' по умолчанию)
order - поле для сортировки структурированных массивов

Пример

Давайте выполним частичное упорядочивание одномерного массива так, чтобы элемент с индексом 3 оказался на своей позиции:

import numpy as np

arr = np.array([7, 1, 5, 3, 9, 2, 8, 4, 6])
res = np.partition(arr, 3)
print(res)

Результат выполнения кода:

[2 1 3 4 9 5 8 7 6]

Четвёртый элемент (с индексом 3) имеет значение 4 - именно таким он был бы в полностью отсортированном массиве. Слева от него находятся элементы меньше или равные 4, справа - больше или равные.

Пример

Давайте укажем несколько индексов, которые должны оказаться на своих местах:

import numpy as np

arr = np.array([7, 1, 5, 3, 9, 2, 8, 4, 6])
res = np.partition(arr, [2, 5])
print(res)

Результат выполнения кода:

[2 1 3 4 5 6 8 7 9]

Элементы с индексами 2 и 5 заняли свои позиции: на третьем месте находится значение 3, на шестом - значение 6. Все элементы между ними также частично упорядочены.

Пример

Давайте выполним частичное упорядочивание по строкам двумерного массива:

import numpy as np

arr = np.array([[7, 1, 5],
				[3, 9, 2],
				[8, 4, 6]])
res = np.partition(arr, 1, axis=1)
print(res)

Результат выполнения кода:

[[1 5 7]
 [2 3 9]
 [4 6 8]]

В каждой строке элемент с индексом 1 оказался на своей позиции. Слева от него находятся меньшие элементы, справа - большие.

Пример

Давайте используем метод partition для массива NumPy:

import numpy as np

arr = np.array([7, 1, 5, 3, 9, 2, 8, 4, 6])
arr.partition(3)
print(arr)

Результат выполнения кода:

[2 1 3 4 9 5 8 7 6]

Метод partition изменяет массив на месте, в отличие от функции partition, которая возвращает новый массив.

Смотрите также

функцию sort,
которая выполняет полную сортировку массива
функцию argpartition,
которая возвращает индексы для частичного упорядочивания
функцию argsort,
которая возвращает индексы для полной сортировки
функцию searchsorted,
которая ищет позиции вставки элементов в отсортированный массив