Sorting is the ordering of a set of similar data in ascending or descending order. Sorting is one of the most pleasant for mental analysis by category algorithms, since the sorting process is very well defined. The sorting algorithms were extensively analyzed, and the way they work is well understood. Unfortunately, due to this scrutiny, sorting is often taken for granted. If you need to sort the data, many programmers simply call the standard qsort () function included in the standard C library. However, different approaches to sorting have different characteristics. Although some sorting methods may be better on average than others, no algorithm is ideal for all cases. Therefore, a wide range of sorting algorithms is a useful addition to the toolkit of any programmer.

It will be useful to briefly discuss why the qsort () call is not a universal solution to all sorting tasks. First, a general purpose function like qsort () cannot be applied in all situations. For example, qsort () sorts only arrays in memory. It cannot sort the data stored in linked lists. Secondly, qsort () is a parameterized function, thanks to which it can process a wide range of data types, but at the same time it therefore works slower than an equivalent function calculated for any one data type. Finally, as you will see, although the quick sort algorithm used in the qsort () function is very effective in general, it may not be the best algorithm in some specific situations.

There are two general categories of sorting algorithms: algorithms that sort objects with random access (for example, arrays or disk files of random access), and algorithms that sort sequential objects (for example, files on disks and tapes or linked lists [1] ). In this chapter, only algorithms of the first category are considered, since they are most useful for the average programmer.

Most often, when sorting data, only part of it is used as the sort key. The key is a piece of information that determines the order of the elements. Thus, the key is involved in comparisons, but when elements are exchanged, the entire data structure is moved. For example, in a mailing list, a zip code can be used as a key, but the entire address is sorted. For simplicity, the following examples will sort the arrays of characters in which the key and the data match. Next, you will see how to adapt these methods to sort data structures of any type.

[1] Depending on this, sorting is called internal or external .

Sort Algorithm Classes

There are three common methods for sorting arrays:

• Exchange
• Selection (selection)
• Insert

To understand how these methods work, imagine a deck of playing cards. To sort cards by swapping [1] , lay them face up on the table and swap cards that are not in order until the whole deck is ordered. In the selection method, place the cards on the table, select the card of the smallest significance and place it in your hand. Then, from the remaining cards, select the card of least importance again and place it on the one that is already in your hand. The process is repeated until all the cards are in the hand; at the end of the process the deck will be sorted. To sort a deck using the insert method, take all the cards in your hand. Put them one by one on the table, inserting each subsequent card in the appropriate position. When all cards are on the table, the deck will be sorted.

[1] That is, exchange sorting .

Evaluation of sorting algorithms

There are many different sorting algorithms. All of them have their positive aspects, but the general criteria for evaluating the sorting algorithm are as follows:

• How quickly does this algorithm sort information on average?
• How fast does it work in the best and worst cases?
• Does he behave naturally or unnaturally?
• Does it swap items with the same key? [one]

Let's take a closer look at these criteria. Obviously, the speed of any sorting algorithm is of great importance. The sorting rate [2] of the array is directly related to the number of comparisons and the number of exchanges that occur during the sorting, and the exchanges take longer. Comparison occurs when one element of the array is compared with another; the exchange occurs when the two elements are swapped. The running time of some sorting algorithms grows exponentially, while the running time of others depends logarithmically on the number of elements.

Hours in the best and worst cases matter if one of these situations occurs quite often. The sorting algorithm often has a good average execution time, but at worst it works very slowly.

The behavior of the sorting algorithm is called natural if the sorting time is minimal for an already ordered list of elements, increases as the degree of list disorder increases, and is maximal when the elements of the list are arranged in reverse order. The workload of the algorithm is estimated by the number of comparisons and exchanges made.

To understand why reordering items with the same key has a specific meaning, imagine a mailing list database sorted by master key and plugged in. The main key is the zip code, and within one zip code entries are ordered by last name. When adding a new address to the list and re-sorting the list, the order of the subkey (that is, the names within the postal codes) should not change. To ensure that this does not happen, the sorting algorithm should not exchange keys with the same value [3] .

Further, the sorting algorithms characteristic for each group with efficiency analysis will be presented. After them, more advanced sorting methods will be demonstrated.

[1] If, in a sorted array, elements with the same keys are in the same order in which they were located in the original array, then the sorting algorithm is called stable , and otherwise unstable .

[2] Synonyms: speed , efficiency .

[3] That is, should be sustainable.