Structures and arrays are the most profitable ways of storing information when working with it. The latter can contain any data of the same type 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 is repeatedly sorted and swapped, and logical or mathematical operations are performed on them. One of the ways to put things in order in an array is bubble sort. This publication will study its C code and permutation logic.
Array sorting algorithm
Bubble sort of a one-dimensional array presents no technical difficulties for a 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 efficient. Its algorithm consists of sequential comparison of numbers and mutual rewriting of cells if the condition is met.
Step by step description of sorting
On the first iteration, two neighboring numbers are gradually compared. If the left is greater, then it is overwritten in places with the right. Minus 8 and 0 do not satisfy the conditions. That is why they do not change places. Zero and 5 also don't work. 5 and 3 fit. However, at such an iteration, the reading frame does not fall on the five, but shifts to the right, since 5 was compared with zero before. This means that the next pair - 3 and 9 - is swapped. Further, the reader is invited to view all the replacements on their own without the author's comments and study the bubble sort algorithm.
As a result of all iterations, the array is gradually sorted, and it happens basically like this: large positive numbers are quickly shifted to the right, while smaller and negative numbers are slowly rearranged to the left. It looks like gas bubbles in liquid quickly float up. Because of this analogy, the algorithm was called bubble sort.
Computational complexity estimate
The ideal sorting algorithm should be as fast as possible. However, it should take a small amount of CPU and memory resources. And a process like bubble sorting an array cannot be the most energy efficient and profitable. Therefore, it has not been widely used. If there are fewer problems with memory at the moment, thenprocessor resources to worry about. Since digital arrays can be not just large, but huge, the consumption of computer resources will be unpredictable.
If bubble sort, in principle, quickly copes with putting things in 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 sort has N-square complexity and is very far from the logarithm of N complexity. In addition, the risk of failure when processing a large array increases the chances of data loss due to cell overwriting. Insertion sort or Shell's algorithm will be much more profitable in this regard.
The following C code in the graphical application allows bubble sort to be implemented. It is rendered as a separate function of the void type. It does not return any values, but uses pointers to swap elements depending on the sort conditions. In this case, the code solves the problem of bubble sorting an array of integers in ascending order.
To perform this function, the user must create an array, which must be filled with the desired values. This can be done manually by setting the dimension and 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 with 100 elements.
Declaring and initializing an array
By setting an integer variable and assigning it the value read from the keyboard, you can limit the number of cells that will be filled. You can also implement the function of entering 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 returned after the scan. The value variable will store a value that 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 sort function call 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 syntax rules of the program. So dataArray is the name of the array to be sorted, and sizeDataArray is its size.
Passing these parameters to the BubleSort() function will cause the actual program to perform operations on sizeDataArray instead of using sizeArray as seen in the figure. This also means that the integer array dataArray will be used in the BubleSort() function. The printArrayFunction() and ArrayIntegerInputFunction() functions are called in a similar way. 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 style of programming, when separate operations are rendered as functions, greatly increases the readability of the code and speeds up its development. In such a program, the filling of the array from the keyboard, its printing and the bubble sort itself are separately taken out. The latter can be used to sort data or as a secondary function to find the minimum and maximum of an array.
In insertion sort, each element is compared in turn and a chain of elements already sorted according to the condition is built. As a result, the result of each subsequent comparison is the search for a cell in which a new value can be placed. But the insertion of each of them is performed in the already sorted part of the array.
This processing is faster and has less computational complexity. The C code is presented on a graphical application.
It is also rendered as a function, which receives as arguments the name of the array that needs to be ordered and the size of the array. Here you can also see how slow bubble sort is. With inserts, similar work is done much faster and has a compact program code.