In working with information, the most advantageous ways of storing it are structures and arrays. The latter can contain any of the same type of data that is convenient to use in the program. They are often used in online stores and in game development. Therefore, the data contained in them are repeatedly sorted and interchanged, and logical or mathematical operations are performed on them. One way to clean up an array is through bubble sorting. This publication will examine its C code and permutation logic.
Array Sort Algorithm
Bubble sorting of a one-dimensional array does not present technical difficulties for the programmer, although it is rarely used due to its low efficiency. It is often considered at the training stage as the simplest. However, it is far from the most effective. Its algorithm consists of sequentially comparing digits and mutually overwriting cells, if the condition is met.
Step-by-step description of sorting
At the first iteration, two adjacent numbers are gradually compared. If the left is larger, then it is overwritten in places with the right. Minus 8 and 0 conditions do not satisfy. Therefore, they do not change places. Zero and 5 are also not suitable. 5 and 3 are suitable. However, at such an iteration, the reading frame does not fall on the top five, but shifts to the right, since 5 were previously compared with zero. This means that the next pair is reversed - 3 and 9. Next, the reader is invited to look at all the replacements on their own without any author’s comments and study the bubble sorting algorithm.
As a result of all iterations, the array is gradually sorted, and this happens mainly as follows: large positive numbers quickly shift to the right, while smaller and negative numbers are slowly rearranged to the left. It looks like gas bubbles in a liquid quickly float up. Because of this analogy, the algorithm was called bubble sorting.
Assessment of computational complexity
An ideal sorting algorithm should be as fast as possible. At the same time, it should take up a small amount of processor and memory resources. And such a process as bubble sorting of an array cannot be the most energy-efficient and profitable. Therefore, he did not find wide application. If there are less problems with memory at the moment, then you should worry about processor resources. Since digital arrays can be not just large, but huge, the consumption of computer resources will be unpredictable.
If bubble sorting, in principle, quickly copes with restoring order in a relatively small array, then in a large one, there may be failures due to resource overruns. This means that the universality property inherent in the algorithm will be violated. Moreover, bubble sorting has N-square complexity and is very far from the logarithm of N complexity. In addition, the risk of a failure while processing a large array increases the chances of data loss due to overwriting cells. Sorting by inserts or the Shell algorithm will be much more profitable in this regard.
Program code
The computer code for the C language indicated on the graphic application allows bubble sorting. It is rendered as a separate function of the void type. It does not return any values, but by using pointers it swaps the elements depending on the sorting conditions. In this case, the code solves the problem of bubble sorting of an array of integers in ascending order.
To perform this function, the user must create an array that must be filled with the necessary values. This can be done manually by setting the dimension and the number of elements at the start of the program. Then you can fill the array with constant values. The second option is to create a universal program by declaring a large one-dimensional array of 100 elements.
Declaring and initializing an array
By setting an integer variable and assigning it a value read from the keyboard, you can limit the number of cells that will be filled. You can also implement the function of inputting array elements by the user from the keyboard using the scanf ("% d", & value) function. In this example, “% d” is a modifier string that tells the compiler that an integer value will be obtained after scanning. The variable value will store the value, which is the size of a one-dimensional integer array.
To use the sorting algorithm, you must pass the name of the array and its size to the function. In the situation presented on the graphical application, the call to the sort function will look like this: BubleSort (dataArray, sizeDataArray). Of course, at the end of the line after the function, you should put a semicolon instead of a period, as required by the rules of the syntax of the program. So, dataArray is the name of the array to sort, and sizeDataArray is its size.
Passing these parameters to the BubleSort () function will lead to the fact that instead of using sizeArray, as can be seen in the figure, in a real program, operations will be performed with sizeDataArray. This also means that the integer dataArray will be used in the BubleSort () function. Similarly, the call to printArrayFunction () and ArrayIntegerInputFunction () occurs. The first is responsible for printing, that is, for outputting elements to the console. And the second is needed to fill it with elements entered by the user from the keyboard.
This programming style, when separate operations are carried out in the form of functions, significantly increases the readability of the code and speeds up its development. In a similar program, the array is filled out separately from the keyboard, its output to print, and the bubble sort itself. The latter can be used to organize data or as a secondary function designed to find the minimum and maximum of the array.
Insertion Sort
In insertion sorting, it is assumed that each element is compared one at a time and a chain is already sorted according to the condition of the elements. As a result, the result of each subsequent comparison is a search for a cell in which a new value can be placed. But each of them is inserted into the already sorted part of the array.
Such processing is faster and has less computational complexity. C code is presented in a graphical application.
It is also made in the form of a function, in which the name of the array in need of ordering and the size of the array are passed as arguments. Here you can see how slow bubble sorting is. Inlays, similar work is much faster and has compact program code.