Bubble sorting of one-dimensional array: algorithm, program code in C language

In working with information the most profitableways of storing it are structures and arrays. The latter can contain any one-type data, which is convenient to use in the program. They are often used in the work of online stores and in the development of games. Therefore, the data contained in them is repeatedly sorted and swapped, and logical or mathematical operations are performed on them. One way to bring order to the array is bubble sorting. This publication will study its C code and the logic of permutations.

Array Sort Algorithm

Technical difficulties for the programmerbubble sorting of a one-dimensional array does not represent, although it is used quite rarely because of its low efficiency. It is more often considered at the training stage as the simplest. However, it is far from being the most effective. Its algorithm consists of alternately comparing the digits and mutually overwriting cells if the condition is met.

Step-by-step sorting description

At the first iteration, twoneighboring numbers. If the left is larger, then it is rewritten in places with the right one. Minus 8 and 0 the conditions do not satisfy. That is why they do not change in places. Zero and 5 also do not fit. 5 and 3 are suitable. However, at this iteration the reading frame does not fall on the top five, but shifts to the right, since 5 before this was compared to zero. This means that the next pair - 3 and 9 changes places. Then the reader is offered to review all substitutions independently without author's comments and to study the algorithm of bubble sorting.

As a result of all the iterations, the array graduallyis sorted, and this is basically the case: large positive numbers move quickly to the right, while smaller and negative ones are slowly shifted to the left. It looks like bubbles of gas in a liquid quickly rise up. Because of this analogy, the algorithm was called bubble sorting.

Estimation of computational complexity

The ideal sorting algorithm should beas fast as possible. At the same time, it should take up a small amount of CPU and memory resources. And such a process as a bubble sorting of an array can not be the most energy efficient and profitable. Because of wide application, he did not find. If there are less problems with the memory at the moment, then the processor resources should be worried. Since digital arrays can be not just large, but huge, then the consumption of computer resources will be unpredictable.

If bubble sorting is, in principle, fastcopes with the establishment of order in a relatively small array, then in large there may be failures due to over-expenditure of resources. This means that the universality property inherent in the algorithm will be violated. And the sorting by a bubble has an N-square complexity and is very far from the logarithm of N complexity. In addition, the risk of failure in processing a large array increases the chances of data loss due to overwriting cells. Much more profitable in this regard will be the insertion sorting or the Shell algorithm.

Software code

The following is in the graphical applicationcomputer code for the C language allows you to perform bubble sorting. It is rendered as a separate function of type void. It does not return any values, but using pointers 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 mustcreate an array that needs to be filled with the desired 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

Assigning an integer variable and assigning itThe value read from the keyboard can limit the number of cells that will be filled. You can also implement the function of entering elements of an array by the user from the keyboard, using the scanf function ("% d", & value). In this example, "% d" is a modifying string that tells the compiler that an integer value will be received after the scan. The variable value will store a value that is the size of a one-dimensional integer array.

To use the sorting algorithm, you shouldto pass in the function the name of the array and its size. In the situation presented in 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 syntax rules of the program. So, dataArray is the name of the array you want to sort, and sizeDataArray is its size.

Passing these parameters to the BubleSort () functionwill result in that instead of using sizeArray, as you can see in the figure, in a real program the operations will be performed with sizeDataArray. This also means that the BubleSort () function will use an integer dataArray. Similarly, the function printArrayFunction () and ArrayIntegerInputFunction () are called. The first is responsible for printing, that is, for output to the console of the elements. And the second is needed to fill it with elements entered by the user from the keyboard.

This style of programming, when isolatedoperations are carried out in the form of functions, significantly increases the readability of code and accelerates its development. In such a program, the array is filled out separately from the keyboard, printed out and the bubble sort itself. The latter can be used to organize the data or as a secondary function designed to find the minimum and maximum of the array.

Insertion sorting

In sorting by the insert methodalternately comparing each element and constructing a chain of items already sorted according to the condition. As a result, the result of each subsequent comparison is the search for a cell into which a new value can be placed. But the insertion of each of them is performed in the already sorted part of the array.

Such processing is faster and has less computational complexity. The C code is presented in the graphical application.

It is also rendered in the form of a function in whichAs arguments, the name of the array that needs to be ordered and the size of the array are transferred. Here you can see how slow the bubble sort is. Inserts similar work is much faster and has a compact code.