Shulou(Shulou.com)06/01 Report--

This article mainly introduces "how to write the code of the bubbling sorting algorithm realized by C language". In the daily operation, I believe that many people have doubts about how to write the code of the bubbling sorting algorithm realized by C language. The editor consulted all kinds of materials and sorted out the simple and easy-to-use operation method. I hope it will be helpful for everyone to answer the doubt of "how to write the code of bubbling sorting algorithm in C language". Next, please follow the editor to study!

1. Problem description

Sort N integers (data is entered by the keyboard) in ascending order.

two。 Analysis of problems

For N numbers, because they are of the same type, we can use an array to store them.

Bubble sorting is the process of comparing and exchanging two adjacent elements to turn an unordered table into an ordered table.

The idea of bubble sorting: first, scan the array back from the header, and compare the size of the two adjacent elements one by one during the scanning process.

If the preceding element is larger than the later element in the adjacent two elements, they are interchanged, which is called eliminating a reverse order.

During the scanning process, the big one of the two adjacent elements is constantly moved back, and finally the largest one in the array is changed to the end of the table, which is exactly where the largest element in the array should be.

Then, in the remaining array elements (nmur1 element), repeat the above process, placing the secondary minor element in the penultimate position.

Repeat the above process until the remaining array elements are 0, and the array becomes ordered.

Assuming that the number of elements in the array is n nn, the total number of comparisons required in the worst case is: (n − 1) + (n − 2) +... + 2 − 1) = n (n − 1) / 2.

3. Algorithm design

The process of bubbling sorting is simply represented by a schematic diagram, and the rules are found from the whole sorting process. N elements only need to be compared with n − once.

Suppose there are seven elements in an array, now sort the seven elements, and you only need to compare for six rounds to get the ordered sequence you want.

The last bold number in the diagram is the number fixed after a round of exchange. The schematic diagram is as follows:

Moving picture demonstration

Now that the process of bubble sorting is clear, let's take a look at a dynamic diagram.

4. Programming design one

The array name is represented by a, the array subscript is represented by j, and the subscript of the two adjacent elements in the array can be expressed as a [j], a [juni1] or a [j-1], a [j].

When using arrays to solve problems, you need to be careful that the array subscript does not cross the bounds.

If you define an integer array int a [n], the value range of the subscript of the array element is 0 ~ (n − 1), and the subscript less than 0 or greater than n − 1 is considered out of bounds.

If adjacent elements are represented by a [j], a [juni1], the range of subscript values is 0 ~ (n − 2).

If a [j-1] and a [j] are used, the range of subscript values is 1 ~ (n − 1).

Design two

The exchange of array elements is also a kind of problem type that is often encountered. In general, we need an intermediate variable to complete this situation. For many beginners, a common mistake is to assign values to two elements directly, without the help of intermediate variables.

Let's start with an example of life:

There is blue ink in the blue ink bottle and red ink in the red ink bottle; now we will put the blue ink in the red ink bottle and the red ink in the blue ink bottle.

The way to do this is to find a white empty bottle (which acts as an intermediate variable in the program):

First pour the blue ink into an empty white bottle: Thoua [I] or Thuma [iTun1]

Then pour the red ink into the blue ink bottle: a [I] = a [I + 1] or a [ionization 1] = a [I]

Finally, pour the blue ink from the white bottle into the red ink bottle: a [I] = t or a [I] = t

After these three steps, the exchange of red ink and blue ink is completed. If you do not use the white empty bottle, directly pour the blue ink into the red ink bottle, or pour the red ink into the blue ink bottle, it is bound to destroy the original stored content.

The first round of exchange can be represented by a simple program segment:

The second round of exchange process (the last element has been determined after the first round of comparison and does not need to be compared again):

The third round of exchange process (the last two elements have been determined and do not need to be compared again):

Conclusion

From the above program segment, it is found that the decision condition of the first round of comparison is j

< n-1； 第二轮为 j < n-2； 第三轮为 j < n-3； 依次类推，第 i 轮的循环判定条件必为 j < n-i。 在编程过程中我们可以用两层循环来控制，第一层循环控制交换的轮数，第二层循环控制每轮需要交换的次数。 5. 流程框架 6. 代码实现 假设有下面一组无序数组，我们要对它进行升序排序 完整代码 #include //冒泡排序函数void BubbleSort(int arr[], int len){ int i; int j; int temp; for (i = 0; i < len - 1; i++) //控制比较的轮数 { for (j = 0; j < len - 1 - i; j++) //控制每轮比较的次数 { if (arr[j] >

Arr [j + 1]) / / two adjacent elements of the array are exchanged {temp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = temp }} / / output function void print (int arr [], int len) {int i; for (I = 0; I < len; itemized +) {printf ("% 3D", arr [I]);}} int main () {int arr [10] = {5L8, 6je, 3je, 2je, 1je, 712jue, 4} BubbleSort (arr, 10); printf ("The data after sorted:\ n"); print (arr, 10); printf ("\ n"); return 0;}

Running result

Code map

7. Problem expansion

In addition to the bubbling sort mentioned above, the commonly used sorting methods include selection sort, insert sort, quick sort and heap sort and so on.

Choose the sorting idea:

Scan the entire linear table, compare the first element in the array with other elements in the first round, and swap if the element is smaller than the first element.

Then compare the first element after the exchange with the subsequent element in the last compared position until it is scanned to the end of the linear table, where the smallest element is selected and swapped to the front of the table (this is where it should be).

In the second round of comparison, it starts with the second element and compares it with the third, the fourth and the last one in turn. In the process of comparison, something smaller than the second element is exchanged, and then compared with the following elements.

Use the same method for the remaining child tables until the child tables are empty. In the worst case, compare n (n − 1) / 2 times.

The selection is sorted as follows

# include / / Select sort void selectSort (int arr [], int len) {int i; int j; for (I = 0; I < len-1; iSum +) {int min = I len / assume that the first element is the smallest for (j = I + 1; j < len) Min +) {if (arr [j] < arr [min]) {min = Jutterbank / subscript to save the smallest element}} / / Exchange int temp = arr [min] Arr [min] = arr [I]; arr [I] = temp;}} / / output void print (int arr [], int len) {for (int I = 0; I < len; I +) {printf ("% 3D", arr [I]);} int main () {int arr [10] = {5, 8, 6, 9, 2, 1, 7, 12, 4} SelectSort (arr, 10); printf ("The data after sorted:\ n"); print (arr, 10); printf ("\ n"); return 0;}

Running result

Code map

The efficiency of different sorting methods is different, and different methods can be chosen under different requirements.

At this point, the study of "how to write the code of the bubble sorting algorithm in C language" is over. I hope to be able to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.