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
- ( = Faculty )
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
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