sortieren

Sorting

In short: Arranging the elements of a data structure into a specific order — usually ascending or descending by a comparison criterion.

In more detail: Sorting algorithms differ greatly in their efficiency for large amounts of data — simple methods like bubble sort are easy to understand but very slow for many elements, while advanced methods (merge sort, quicksort) scale significantly more efficiently. Most languages already ship with heavily optimised sorting functions in their standard library, so writing your own sorting algorithm is rarely necessary in practice.

In Depth

A simple, easy-to-follow sorting method is bubble sort: it repeatedly compares neighbouring elements and swaps them if they’re in the wrong order — after enough passes, the largest element “bubbles” upward like a bubble:

def bubble_sort(list_):
    n = len(list_)
    for i in range(n):
        for j in range(n - i - 1):
            if list_[j] > list_[j + 1]:
                list_[j], list_[j + 1] = list_[j + 1], list_[j]
    return list_

Bubble sort is easy to understand and implement, but with O(n²) (see Algorithms) extremely slow for large lists — doubling the list size roughly quadruples the time needed. In practice, it’s used almost exclusively for learning purposes, not in real production code.

For sorting, there are two important properties relevant beyond pure speed:

• Stability: a stable sorting algorithm preserves the relative order of equal elements. If you sort a list of people first by last name and then (stably) by first name, for example, people with the same first name stay sorted by last name — for an unstable algorithm, this order wouldn’t be guaranteed.
• In-place vs. additional memory: some algorithms sort directly within the original data structure (little additional memory needed), others build an entirely new, sorted structure (more memory, but sometimes easier to parallelise).

Because the built-in sorting functions of standard libraries (usually variants of merge sort or quicksort) have been optimised and thoroughly tested for years, writing your own sorting algorithm in real production code is almost never a good idea — unless you have to sort by a very specific criterion not supported by default, for which most libraries anyway offer a way to specify a custom comparison criterion (instead of a whole custom algorithm).

See also: Advanced Sorting, Algorithms, TreeSet