Sorting is an arrangement of objects in a certain order, for example, in descending order or in ascending order. In general, the ordering of elements is the most common data manipulation, which facilitates the further search for the necessary information. This applies in many ways to various database management systems. Sorting algorithms currently exist in large numbers, although they have similar features (steps): comparing and rearranging elements in pairs until the sequence becomes ordered.
Sorting algorithms can be classified into internal and external. The first are characterized by the fact that all sortable elements are placed in RAM and it is possible to get random access to any of them. The latter can work with data located in external memory (in files). Access to such elements can be implemented sequentially.
It is more convenient to sort the elements when they are in the structure of a one-dimensional array. Each such element has a serial number, and the array element is accessed by index. Sorting algorithms in this case are the simplest and most understandable for use.
Consider the internal sorting algorithm in descending order by the bubble method and its improved version, which differs in the time spent sorting. Bubble sorting actually has a lot of names. It is also called the linear sorting method or the exchange sorting method of choice. But, however, the point is not the name. Why a bubble? Once in the water, an air bubble will pop up, as it is lighter. So, for example, when sorting in ascending order, the smallest of the elements will be at the top.
Consider the first version of the algorithm for sorting an array using the bubble method. The verbal algorithm for sorting an array that has the identifier mas and consists of N elements is as follows:
1. Put in place of the first element (mas [1]) the largest element of the array. To do this, we will compare it in turn with all the remaining elements (mas [2], mas [3] ... mas [N]). If it turns out that any of the remaining elements is greater than mas [1], then you need to swap them (via the additional variable buf).
2. Excluding from consideration the element mas [1], repeat step 1 for the element mas [2].
3. Repeat these steps for all items except the last.
Implementation of the bubble sorting algorithm in the Pascal programming language:
About the second option (advanced bubble method), we can say that this is a quick sort algorithm . So, if you try to use it to sort an already sorted array, the algorithm will finish its work after the first pass through the elements of the array. This means that we will not waste the computing resources of the system and time on meaningless comparison of elements.
Here is the implementation of this sorting algorithm for the Pascal programming language:
So, sorting algorithms are a means of ordering data sequences. When choosing a particular algorithm, costs should be considered in terms of time and system resources.