numpy.sort
Функция sort() возвращает отсортированную копию массива.
Параметры: a — массив NumPy или подобный массиву объект. Исходный массив. axis — целое число (необязательный параметр). Определяет ось вдоль которой выполняется сортировка элементов. Если равен None, то сортировка выполняется по сжатому до одной оси представлению исходного массива. По умолчанию axis = -1 , что соответствует сортировке по последней оси массива. kind — строка (необязательный параметр). Одна строка из множества <'quicksort', 'mergesort', 'heapsort', 'stable'>, которая указывает на алгоритм сортировки. Значение ‘stable’ приводит к автоматическому выбору устойчивого, лучшего алгоритма для типа данных сортируемого массива. По умолчанию kind = ‘quicksort’ . order — строка или список строк (необязательный параметр). В случае, когда массив a является структурированным, и его полям присвоено имя, то данный параметр позволяет указать порядок в котором они должны учавствовать в сортировке Если указаны не все поля, то неуказанные будут использоваться в том порядке в котором они перечислены в dtype структурированного массива. Возвращает: ndarray — массив NumPy отсортированную копию исходного массива a с той же формой и типом данных.
Замечание
Данная функция обладает эквивалентным методом класса ndarray, т.е. np.sort(a) равносильно вызову метода a.sort() , но в отличие от функции данный метод не возвращает копию, а меняет исходный массив:
Параметр kind позволяет выбрать один из трех алгоритмов сортировки: ‘quicksort’, ‘mergesort’ или ‘heapsort’. Каждый из алгоритмов делает временную копию данных при выполнении сортировки по всем осям кроме последней, так что сортировка только по последней оси выполняется быстрее всего и занимает меньше всего места.
Сортировка в массивах содержащих действительные числа и nan всегда сначала выполняется над действительными числами, а уже затем над nan.
Сортировка комплексных чисел выполняется лексикографически: если действительная и мнимая часть не равна nan то сортировка выполняется по действительной части, но если действительные части равны, то порядок определяется их мнимыми частями. Расширенный порядок сортировки: [R + Rj, R + nan, nan + Rj, nan + nan], где R — действительное число.
В NumPy, начиная с версии 1.12.0. алгоритм quicksort был заменен на алгоритм introsort.
Примеры
Сортировка одномерных массивов приводит к вполне ожидаемому результату:
А вот многомерные массивы могут быть отсортированы по разным осям (направлениям). Например, двумерные массивы могут быть отсортированы как по столбцам так и по строкам:
Трехмерные массивы, грубо говоря, могут быть отсортированы по «длине», «ширине» и «высоте»:
Если выполняется сортировка структурированного массива, то параметр order позволяет указать по какому полю выполнять сортировку:
Как отсортировать матрицу python
Credits: ITMO University
New in version 1.17.0.
Timsort is added for better performance on already or nearly sorted data. On random data timsort is almost identical to mergesort. It is now used for stable sort while quicksort is still the default sort if none is chosen. For timsort details, refer to CPython listsort.txt. ‘mergesort’ and ‘stable’ are mapped to radix sort for integer data types. Radix sort is an O(n) sort instead of O(n log n).
quicksort
New in version 1.12.0.
quicksort has been changed to introsort. When sorting does not make enough progress it switches to heapsort. This implementation makes quicksort O(n*log(n)) in the worst case.
numpy.matrix.sort#
Sort an array in-place. Refer to numpy.sort for full documentation.
Parameters axis int, optional
Axis along which to sort. Default is -1, which means sort along the last axis.
Sorting algorithm. The default is ‘quicksort’. Note that both ‘stable’ and ‘mergesort’ use timsort under the covers and, in general, the actual implementation will vary with datatype. The ‘mergesort’ option is retained for backwards compatibility.
Changed in version 1.15.0: The ‘stable’ option was added.
When a is an array with fields defined, this argument specifies which fields to compare first, second, etc. A single field can be specified as a string, and not all fields need be specified, but unspecified fields will still be used, in the order in which they come up in the dtype, to break ties.
Return a sorted copy of an array.
Indirect stable sort on multiple keys.
Find elements in sorted array.
See numpy.sort for notes on the different sorting algorithms.
Use the order keyword to specify a field to use when sorting a structured array:
Sorting Arrays
Up to this point we have been concerned mainly with tools to access and operate on array data with NumPy. This section covers algorithms related to sorting values in NumPy arrays. These algorithms are a favorite topic in introductory computer science courses: if you’ve ever taken one, you probably have had dreams (or, depending on your temperament, nightmares) about insertion sorts, selection sorts, merge sorts, quick sorts, bubble sorts, and many, many more. All are means of accomplishing a similar task: sorting the values in a list or array.
For example, a simple selection sort repeatedly finds the minimum value from a list, and makes swaps until the list is sorted. We can code this in just a few lines of Python:
As any first-year computer science major will tell you, the selection sort is useful for its simplicity, but is much too slow to be useful for larger arrays. For a list of $N$ values, it requires $N$ loops, each of which does on order $\sim N$ comparisons to find the swap value. In terms of the «big-O» notation often used to characterize these algorithms (see Big-O Notation), selection sort averages $\mathcal
Even selection sort, though, is much better than my all-time favorite sorting algorithms, the bogosort:
This silly sorting method relies on pure chance: it repeatedly applies a random shuffling of the array until the result happens to be sorted. With an average scaling of $\mathcal
Fortunately, Python contains built-in sorting algorithms that are much more efficient than either of the simplistic algorithms just shown. We’ll start by looking at the Python built-ins, and then take a look at the routines included in NumPy and optimized for NumPy arrays.
Fast Sorting in NumPy: np.sort and np.argsort ¶
Although Python has built-in sort and sorted functions to work with lists, we won’t discuss them here because NumPy’s np.sort function turns out to be much more efficient and useful for our purposes. By default np.sort uses an $\mathcal
To return a sorted version of the array without modifying the input, you can use np.sort :
If you prefer to sort the array in-place, you can instead use the sort method of arrays:
A related function is argsort , which instead returns the indices of the sorted elements:
The first element of this result gives the index of the smallest element, the second value gives the index of the second smallest, and so on. These indices can then be used (via fancy indexing) to construct the sorted array if desired:
Sorting along rows or columns¶
A useful feature of NumPy’s sorting algorithms is the ability to sort along specific rows or columns of a multidimensional array using the axis argument. For example:
Keep in mind that this treats each row or column as an independent array, and any relationships between the row or column values will be lost!
Partial Sorts: Partitioning¶
Sometimes we’re not interested in sorting the entire array, but simply want to find the k smallest values in the array. NumPy provides this in the np.partition function. np.partition takes an array and a number K; the result is a new array with the smallest K values to the left of the partition, and the remaining values to the right, in arbitrary order:
Note that the first three values in the resulting array are the three smallest in the array, and the remaining array positions contain the remaining values. Within the two partitions, the elements have arbitrary order.
Similarly to sorting, we can partition along an arbitrary axis of a multidimensional array:
The result is an array where the first two slots in each row contain the smallest values from that row, with the remaining values filling the remaining slots.
Finally, just as there is a np.argsort that computes indices of the sort, there is a np.argpartition that computes indices of the partition. We’ll see this in action in the following section.
Example: k-Nearest Neighbors¶
Let’s quickly see how we might use this argsort function along multiple axes to find the nearest neighbors of each point in a set. We’ll start by creating a random set of 10 points on a two-dimensional plane. Using the standard convention, we’ll arrange these in a $10\times 2$ array:
To get an idea of how these points look, let’s quickly scatter plot them:
Now we’ll compute the distance between each pair of points. Recall that the squared-distance between two points is the sum of the squared differences in each dimension; using the efficient broadcasting (Computation on Arrays: Broadcasting) and aggregation (Aggregations: Min, Max, and Everything In Between) routines provided by NumPy we can compute the matrix of square distances in a single line of code:
This operation has a lot packed into it, and it might be a bit confusing if you’re unfamiliar with NumPy’s broadcasting rules. When you come across code like this, it can be useful to break it down into its component steps:
Just to double-check what we are doing, we should see that the diagonal of this matrix (i.e., the set of distances between each point and itself) is all zero:
It checks out! With the pairwise square-distances converted, we can now use np.argsort to sort along each row. The leftmost columns will then give the indices of the nearest neighbors:
Notice that the first column gives the numbers 0 through 9 in order: this is due to the fact that each point’s closest neighbor is itself, as we would expect.
By using a full sort here, we’ve actually done more work than we need to in this case. If we’re simply interested in the nearest $k$ neighbors, all we need is to partition each row so that the smallest $k + 1$ squared distances come first, with larger distances filling the remaining positions of the array. We can do this with the np.argpartition function:
In order to visualize this network of neighbors, let’s quickly plot the points along with lines representing the connections from each point to its two nearest neighbors:
Each point in the plot has lines drawn to its two nearest neighbors. At first glance, it might seem strange that some of the points have more than two lines coming out of them: this is due to the fact that if point A is one of the two nearest neighbors of point B, this does not necessarily imply that point B is one of the two nearest neighbors of point A.
Although the broadcasting and row-wise sorting of this approach might seem less straightforward than writing a loop, it turns out to be a very efficient way of operating on this data in Python. You might be tempted to do the same type of operation by manually looping through the data and sorting each set of neighbors individually, but this would almost certainly lead to a slower algorithm than the vectorized version we used. The beauty of this approach is that it’s written in a way that’s agnostic to the size of the input data: we could just as easily compute the neighbors among 100 or 1,000,000 points in any number of dimensions, and the code would look the same.
Finally, I’ll note that when doing very large nearest neighbor searches, there are tree-based and/or approximate algorithms that can scale as $\mathcal
Aside: Big-O Notation¶
Big-O notation is a means of describing how the number of operations required for an algorithm scales as the input grows in size. To use it correctly is to dive deeply into the realm of computer science theory, and to carefully distinguish it from the related small-o notation, big-$\theta$ notation, big-$\Omega$ notation, and probably many mutant hybrids thereof. While these distinctions add precision to statements about algorithmic scaling, outside computer science theory exams and the remarks of pedantic blog commenters, you’ll rarely see such distinctions made in practice. Far more common in the data science world is a less rigid use of big-O notation: as a general (if imprecise) description of the scaling of an algorithm. With apologies to theorists and pedants, this is the interpretation we’ll use throughout this book.
Big-O notation, in this loose sense, tells you how much time your algorithm will take as you increase the amount of data. If you have an $\mathcal
For our purposes, the N will usually indicate some aspect of the size of the dataset (the number of points, the number of dimensions, etc.). When trying to analyze billions or trillions of samples, the difference between $\mathcal
Notice that the big-O notation by itself tells you nothing about the actual wall-clock time of a computation, but only about its scaling as you change N. Generally, for example, an $\mathcal
Even this loose version of Big-O notation can be very useful when comparing the performance of algorithms, and we’ll use this notation throughout the book when talking about how algorithms scale.
numpy.matrix.sort#
Sort an array in-place. Refer to numpy.sort for full documentation.
Parameters : axis int, optional
Axis along which to sort. Default is -1, which means sort along the last axis.
Sorting algorithm. The default is ‘quicksort’. Note that both ‘stable’ and ‘mergesort’ use timsort under the covers and, in general, the actual implementation will vary with datatype. The ‘mergesort’ option is retained for backwards compatibility.
Changed in version 1.15.0: The ‘stable’ option was added.
When a is an array with fields defined, this argument specifies which fields to compare first, second, etc. A single field can be specified as a string, and not all fields need be specified, but unspecified fields will still be used, in the order in which they come up in the dtype, to break ties.
Return a sorted copy of an array.
Indirect stable sort on multiple keys.
Find elements in sorted array.
See numpy.sort for notes on the different sorting algorithms.
Use the order keyword to specify a field to use when sorting a structured array: