Popular recipes tagged "sorting" but not "functional"

Fast min/max function (Python)

2011-10-22T18:40:32-07:00

Python recipe 577916 by Raymond Hettinger (minmax, sorting).

Minimizes the number of comparisons to compute the minimum and maximum of a dataset. Uses 1.5 compares for every element, improving on the more obvious solution that does 2 comparisons per element.

Dependency resolution (Python)

2016-04-14T12:58:40-07:00

Python recipe 580642 by Mike 'Fuzzy' Partin (compare, dependency, sort, sorting).

This recipe shows how to take a list of objects, each with their own list of dependencies, and resolve them to proper order. It includes some poor mans circular dependency detection (very poor mans).

Topological Sort (Python)

2012-09-27T12:21:23-07:00

Python recipe 578272 by Sam Denton (algorithm, sort, sorting, topological, toposort).

A topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

lazy DSU (Python)

2012-09-12T04:49:59-07:00

Python recipe 578259 by Chris Smith (dsu, sorting).

sort a sequence by applying decoration only as needed

Fast Sorting of n dimensional array by first dimension (Python)

2012-03-14T15:14:11-07:00

Python recipe 578074 by Garrett (argsort, lists, numpy, python, sorting).

I have looked far and wide for code for fast sorting of n dimensional arrays by the first element, for example if I had the array:
ray = [[1,2,3,7,5][10,11,12,13,14]]

I would want it to come out as ray = [[1,2,3,5,7][10,11,12,14,13]]

There are several ways to do this. One is zipped = zip(ray) zipped.sort() ray = zip(zipped)

but this is extremely slow. Numpy has a much faster way to do it, but it wasn't immediately apparent.

if the above were a numpy array you could simply do the following: indexes = numpy.argsort(ray[0]) for n in xrange(len(ray)) ray[n] = ray[n][indexes]

I did a time test of the two methods below.

Sorting a dict's items and keys (Python)

2012-02-04T04:23:01-08:00

Python recipe 578031 by George V. Reilly (dictionary, sorting).

icalendar uses its own CaselessDict as the base of many classes. I needed to produce the keys and items in a canonical order, so that certain keys would appear first.

Sleepsort (Python)

2011-06-17T05:17:22-07:00

Python recipe 577756 by Raymond Hettinger (sorting, threads). Revision 2.

Funky sort routine to demonstrate Python's threading basics.

Sleepsort with processes and pipes (Python)

2011-06-17T02:37:58-07:00

Python recipe 577758 by Benjamin Peterson (process, sorting, unix). Revision 2.

Sleepsort is a sorting algorithm that uses the system sleep syscall in a very creative fashion.

This is the same algorithm as recipe 577756 but using *nix processes instead of threads.

Topological Sort (Python)

2010-09-28T19:22:27-07:00

Python recipe 577413 by Paddy McCarthy (algorithm, sorting, topological).

Given items that depend on other items, a topological sort arranges items in order that no one item precedes an item it depends on. In this example items are strings and dependencies are expressed in a dictionary whose keys are items and whose values are a set of dependent items. Note that the dict may contain self-dependencies (which are ignored), and dependent items that are not also dict keys, such as the item 'ieee'.

Sorting big files the Python 2.6 way (Python)

2009-05-30T21:51:09-07:00

Python recipe 576755 by Gabriel Genellina (binary, file, sort, sorting, text). Revision 3.

This is just a rewrite of Recipe 466302 "Sorting big files the Python 2.4 way", taking advantage of heapq.merge, context managers, and other niceties of newer Python versions. It can be used to sort very large files (millions of records) in Python. No record termination character is required, hence a record may contain embedded binary data, newlines, etc. You can specify how many temporary files to use and where they are located.

Total Ordering: Class Decorator for Filling in Rich Comparison Methods When Only One is Implemented (Python)

2008-10-28T11:54:42-07:00

Python recipe 576529 by Michael Foord (class_decorator, comparison, decorator, ordering, sorting). Revision 5.

total_ordering and force_total_ordering are class decorators for Python 2.6 & Python 3.

They provides all the rich comparison methods on a class by defining any one of '__lt__', '__gt__', '__le__', '__ge__'.

total_ordering fills in all unimplemented rich comparison methods, assuming at least one is implemented. __lt__ is taken as the base comparison method on which the others are built, but if that is not available it will be constructed from the first one found.

force_total_ordering does the same, but having taken a comparison method as the base it fills in all the others - this overwrites additional comparison methods that may be implemented, guaranteeing consistent comparison semantics.

Sorting a list of dictionary based on a key value (Python)

2008-08-20T03:30:37-07:00

Python recipe 576433 by riteshn (dictionary, list, sorting).

Here is a quick and dirty way to sort a list of dictionary based on a key value.