Stability (sorting process)

A stable sorting method is a sorting algorithm that preserves the order of the data records whose sorting keys are the same.

If, for example, a list of alphabetically sorted personal files is re-sorted according to the date of birth, then all persons with the same date of birth remain sorted alphabetically under a stable sorting process.

If you want to sort with an unstable sorting process, such as Quicksort , and keep the order of the data records with the same key, you can make do with adding a sequence number to the data records and giving this field the lowest rank in the sort key. However, it is less time-consuming to use a stable sorting process.

Stable and unstable sorting procedures behave in the same way if the multiset of the key in the input is a set , i.e. there are no duplicates among the keys; likewise if data records with the same key can not be distinguished in any way - for example, because the key encompasses the entire data record. A multitude of numbers or names, for example, can be sorted with a stable or unstable sorting process, the result is always the same:

Stable or unstable sorting process:

  4       1
  3       2
  5       3
  3   →   3
  2       3
  1       4
  3       5

Stable or unstable sorting method (alphabetically):

  Carla        Annette
  Annette  →   Birgit
  Birgit       Carla

However, if you combine names and numbers to form a data record and sort only according to a partial key, e.g. numbers, then there are different options for the order given the same keys. A stable procedure chooses the order that maintains the original order of the names if the keys are the same, for example

Stable sorting process by numbers:

  1 Anton       1 Anton
  4 Karl        1 Paul
  3 Otto        3 Otto
  5 Bernd   →   3 Herbert
  3 Herbert     4 Karl
  8 Alfred      5 Bernd
  1 Paul        8 Alfred

Unstable sorting process by numbers:

  1 Anton        1 Paul         1 Anton        1 Paul            1 Anton
  4 Karl         1 Anton        1 Paul         1 Anton           1 Paul
  3 Otto         3 Otto         3 Herbert      3 Herbert         3 Otto
  5 Bernd   →    3 Herbert oder 3 Otto    oder 3 Otto       oder 3 Herbert
  3 Herbert      4 Karl         4 Karl         4 Karl            4 Karl
  8 Alfred       5 Bernd        5 Bernd        5 Bernd           5 Bernd
  1 Paul         8 Alfred       8 Alfred       8 Alfred          8 Alfred

If the sorting is unstable, Paul can stand in front of Anton or Herbert in front of Otto.

Application in data processing

In computer science . Are very common so-called tables before, d. H. Sequences (collections, files ) of data records divided into fields , in which each data record stands for an individual and a field for a characteristic of this individual. Many application programs, e.g. B. from databases , and spreadsheet programs support the selection of individual characteristics ("table columns") as a sorting term ( key ).

A combined sorting key from two columns, e.g. in the order of precedence ( file type , file size ) leads to the same result as two sortings according to one column each, first according to file size and in the second sorting run according to file type . The second sorting run must receive the order created by the first run in the sense explained above, m. a. W .: the second run must sort in a stable manner.

Example: File manager (similar to Windows Explorer ):

Filename	File type	Modification date	File size
a	doc	1999	20th
u	doc	2018	70
k	txt	2013	25th
c	doc	2013	15th
r	txt	1800	20th

In the case of individual sorting, the lower-ranking keys (fields) must be sorted first. Such an individual sorting can be done by clicking for ascending (displayed as ▴ after the sorting run) resp. two clicks for descending (▾) on the feature name in the title bar.

comment

If the user's browser sorts in a stable manner, then after clicking on the File type column, the order in the File name column is : a, u, c, k, r.

What is the maximum number of different sortings (with 4 columns and stable sorting)?

If the Explorer always sorts stable , then there is a (single) sort after each of the

${\displaystyle {\binom {4}{4}}\cdot 4!+{\binom {4}{3}}\cdot 3!+{\binom {4}{2}}\cdot 2!+{\binom {4}{1}}\cdot 1!=24+24+12+4=64}$         ( = Faculty ) ${\displaystyle !}$

Combinations and sequences of the 4 fields are equivalent to a suitably selected sequence of a maximum of 4 sorting according to a single field. If the sorting directions ascending / descending are important, then come

${\displaystyle {\binom {4}{4}}\cdot 2^{4}\cdot 4!+{\binom {4}{3}}\cdot 2^{3}\cdot 3!+{\binom {4}{2}}\cdot 2^{2}\cdot 2!+{\binom {4}{1}}\cdot 2^{1}\cdot 1!=384+192+48+8=632}$

Combinations together.

Examples

Stable sorting process:

• Binary Tree Sort
• Bubble sort
• Counting location
• Cocktail location
• Gnome location
• Insertion location
• Merge sort
• Natal variety
• Shakersort

Unstable sorting processes:

• Bogosort
• Combsort
• Heapsort
• Introsort
• Quicksort
• Selection location
• Shellsort
• Smoothsort
• Slow sort
• Stoogesort

See also

• in-place