What is radix variety in computer science

Sorting algorithms

There's a general one here Sorting Algorithm Overview and a Explanation of the most important terms. What is actually behind sorting processes in IT and in which two types can they be subdivided? What does a unstable and stable sorting process out? This question is simply explained with an example. At the end there is all the important information about the complexity and the Properties of various sorting algorithms at a glance.

Sorting algorithm

A sorting algorithm (in English sort algorithm or sorting algorithm) is a sorting method in computer science that has one Arrayorder according to the desired search criterion should. But that only works for a strictly weak order, called either on lexicographical basis - so by letter at one String or numerically - that is, by numbers. For implementation, a set is required that is to be sorted, but which also represents the input at the same time. The main goal of a sorting algorithm is on the one hand to order a given quantity efficiently and on the other hand to pass the sorted list as output.

Two types of sorting algorithms

Sorting processes can generally differ in the basis of the working method. On the one hand, sorting algorithms comparison-based work or not. That is, part of the sorting algorithms Compare items on the list used to swap the items in the correct order accordingly. At the non-settlement-based method lies the Focus on the conditioned input. Here is an overview of the division of the sorting algorithms of both variants - comparison-based and address-based.

If you want to know more about the individual sorting methods, just have a look at ours Videos to do this! There you will also find within our posts to the different Sorting algorithms Java source codes.

Stable sorting process

Sorting methods can be additional differentiated between stable and unstable sorting become. Stable sorting methods have the focus that the The order of the records remains the same, whose sort keys are also the same. But what does that mean exactly?

Suppose you want to sort the alphabetically ordered list of club members in a sports club by year of birth. Then stable sorting processes ensure that the club members with the same year of birth still remain sorted in alphabetical order. The procedure sorts in first priority according to the year of birth and the second priority is the alphabetical order. In this case, Alex stands in front of Julian.

Stable sorting process by numbers

1995Alex1995Alex
1997Christina1995Sebastian
1999Hannah1997Christina
1997Julian1997Julian
1995Sebastian1999Hannah

Examples

Examples of a stable sorting process are:

Unstable sorting process

In the unstable sorting process, exactly the opposite is the case. Back to the club members again. In this case different end results after a sorting process occurrence, hence the name unstable. Therefore it is also possible that Julian stands in front of Alex and Sebastian in front of Christina.

Unstable sorting methods by numbers

1995 Alex1995 Alex1995 Julian1995 Alex1995 Julian
1997 Christina1995 Julian1995 Alex1995 Juian1995 Alex
1999 Hannah1997 Christina1997 Christina1997 Sebastian1997 Sebastian
1995 Julian1997 Sebastian1997 Sebastian1997 Christina1997 Christina
1997 Sebastian1999 Hannah1999 Hannah1999 Hannah1999 Hannah

Examples

Examples of an unstable sorting process are:

complexity

When it comes to sorting methods, one can always refer to the term complexity bump. This is really just a matter of the fact that the different algorithms are just sort data volumes with varying degrees of efficiency can. Which sorting process can ultimately be called the “best sorting algorithm” must always be decided individually and depending on the situation. Two decision factors with regard to the complexity are the sorting algorithms, runtime and the required storage space.

Sorting algorithms runtime

The efficiency of the sorting algorithms is in most cases of the Initial state dependent - So how is the amount of data arranged during input. There is always between Best case, average case and worst case differentiated. For example, if the list is sorted from the start, most sorting algorithms need less time to sort. So that would be the best case, since it makes the algorithm even more efficient.

Space complexity - in-place

In addition, some of the methods also require the stored list of data additional storage space for intermediate results. In relation to this, a distinction is also made between whether a sorting process in-place is working. That actually just means that the additional storage requirements regardless of the amount of data and is therefore mostly constant and low. Understandably, with out-of-place it is exactly the opposite.

Sorting algorithms comparison

Here you can now have a look at all the properties of the various sorting algorithms in terms of complexity and stability in comparison.

Comparison-based sorting