Latest recipes tagged "sort"

Ordered Listbox for Tkinter (Python)

2017-02-11T19:01:52-08:00

Python recipe 580756 by Miguel Martínez López (listbox, ordered, sort, sorted, tkinter). Revision 6.

Listbox megawidget showing ordered strings. It's possible to ignore case. I also provided an auto scrollbar option.

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 sorting again (Python)

2013-03-06T19:21:11-08:00

Python recipe 578406 by yota (algorithm, graph, python3, sort, topological). Revision 9.

Topological sorting is the answer to the following question : in a direct acyclic graph, how can I pick up nodes "in order", such as upstream nodes are always before downstream ones ? Many solutions may exists, many algorithms too.

Alas, it seems I'm too stupid to understand already proposed recipes on topological sorting. Hopefully I do grasp the "write once, read many" concept.

Here, you will find a plain algorithm, optimized only for code clarity, of a topological sorting for direct acyclic graphs, implemented in python from the pseudo code found on wikipedia:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

Only tested with python3.2, should work with other versions. Be careful, code indented with tabs, since space is evil è_é

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).

Python Binary Search Tree (Python)

2011-08-08T00:15:09-07:00

Python recipe 577830 by sivarama sarma (algorithms, maximum, minimum, search, sort).

A data structure that holds a sorted collection of values, and supports efficient insertion, deletion, sorted iteration, and min/max finding. Values may sorted either based on their natural ordering, or on a key function (specified as an argument to the search tree's constructor). The search tree may contain duplicate values (or multiple values with equal keys) -- the ordering of such values is undefined.

This implementation was made with efficiency in mind. In particular, it is more than twice as fast as the other native-Python implementations I tried (which all use objects to store search tree nodes).

BitSort (Python)

2011-06-19T14:03:56-07:00

Python recipe 577763 by wong2 (sort).

BitSort in python. using bitarray library

SleepSort (Timer version) (Python)

2011-06-18T05:37:06-07:00

Python recipe 577762 by wong2 (algorithms, interest, sort).

Python version sleep sort by using threading.Timer

heap sort (Python)

2011-05-12T01:39:18-07:00

Python recipe 577688 by huang chongdi (heap, sort).

a python version of heap sort

naive natural sort (Python)

2011-08-13T16:47:36-07:00

Python recipe 577679 by Romain Dartigues (ascii, sort).

I wrote this after reading The Alphanum Algorithm (http://www.davekoelle.com/alphanum.html) by David Koelle a few years ago; my goal was to improve the performances of the Python version of his scripts.

My version is approximatly 10 times faster than it's alphanum.py and about 3 times faster than the alphanum.py_v2.4 on my computer, yielding the same results (for non-unicode at least).

Note: see the version of wizkid in the comments which is even faster.

Python Binary Search Tree (Python)

2011-01-10T02:27:08-08:00

Python recipe 577540 by Edward Loper (algorithms, maximum, minimum, search, sort). Revision 2.

Sort file (with unique option) (JavaScript)

2010-05-30T21:47:36-07:00

JavaScript recipe 577247 by Glenn Jenkins (file, komodo, sort, unique).

This will sort the lines in the current document into alphabetical order. It doesn't apply any special rule (so 5 will come after 42).

On running, it asks if you want a unique sort (Cancel for no, Ok for yes), in which case it'll remove duplicate lines.

Merge multiple (potentially infinite) sorted inputs into a single sorted output (Python)

2010-04-01T04:54:16-07:00

Python recipe 577041 by Gabriel Genellina (algorithm, algorithms, merge, sort). Revision 4.

Merge a (possibly infinite) number of already sorted inputs (each of possibly infinite length) into a single sorted output.

Similar to heapq.merge and sorted(itertools.chain(*iterables)).

Like heapq.merge, returns a generator, does not pull the data into memory all at once, and assumes that each of the input iterables is already sorted (smallest to largest).

Unlike heapq.merge, accepts an infinite number of input iterables, but requires all of them to come in ascending order (that is, their starting point must come in ascending order).

In addition, accepts a key function (like sorted, min, max, etc.)

Functional selection sort (Python)

2009-09-29T13:34:35-07:00

Python recipe 576917 by pavel (algorithm, algorithms, functional, lambda, reduce, selection, sort, sorting). Revision 3.

This is a variant of selection sort without using for-statements. Do you like it? :-)

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.

Sort sections and keys in .ini file (Python)

2008-12-19T05:46:05-08:00

Python recipe 576587 by Michal Niklas (config, file, ini, sort). Revision 3.

I use this program when I want to make .ini file more readable or compare two .ini files

Sort strings containing german umlauts in correct order (Python)

2008-09-13T14:28:54-07:00

Python recipe 576507 by Andreas Maier (din5007, sort, string, umlaut). Revision 13.

A function which implements sort keys for the german language according to DIN 5007.

Arbitrary order attribute writing with ElementTree (Python)

2008-08-01T19:24:34-07:00

Python recipe 576403 by Orri Ganel (attribute, element, elementtree, element_tree, etree, order, sort, write, writing, xml). Revision 5.

Modified version of ElementTree with two additional parameters to the write() method: "sortflag" and "sortcmp". "sortflag" defaults to "default", which results in unmodified behavior. "sortcmp" defaults to None, which results in unmodified behavior. See discussion for usage and justification. Changes made begin on line 655.

EDIT: in most cases, unless sortflag happened to be intended for the root, it would be ignored; added sortflag and sortcmp to self._write() call on line 724. Expect another revision in the near future to allow for specifying different orders for different xml tags.

EDIT, the second: Added tag-specific ordering.