preface

C: In this era, algorithm, though not a household name, is a new word that most people often hang on their lips.

Such as: beauty algorithm, face recognition algorithm, recommendation algorithm, compression algorithm…. , we often hear people lament the power of algorithms.

“How impressive! I just looked at the bag on x-treasure and a bunch of bag recommendations came.” (Recommendation algorithm)

“Don’t forget to open my face for photos!!” (Beauty algorithm)

We have introduced data structure in the first two chapters. Data structure and algorithm are inseparable. In this chapter, Teacher Cha will take you to introduce algorithm.

Introduction of algorithm

Description of algorithm

So what is an algorithm?

Algorithm refers to the accurate and complete description of problem solving scheme and a series of clear instructions to solve problems. Algorithm represents the strategy mechanism to solve problems in a systematic way. In other words, the required output can be obtained in a limited time for a given specification of the input. Different algorithms may perform the same task with different time, space, or efficiency. The advantages and disadvantages of an algorithm can be measured by space complexity and time complexity. [1]

To understand what an algorithm is, we need to imagine a scenario. Thousands of years ago, an ancestor tried to make his own bread based on his memory of how his late grandmother made bread. But he really didn’t know what to do. He hesitated, first plunging the kernel into boiling water, then thinking to himself that this might be a bad idea. The ancestor’s dilemma is the one we all face — a problem we don’t know how to solve. We think of solutions, we try, we experiment, we find a little serendipity, we succeed… Or fail.

However, that’s not how real bakers do it. They don’t re-bake every loaf of bread because they already know how to bake bread by heart. Thanks to the bread recipe, bakers can provide us with bread every day. In fact, human civilization developed not only because some people invented things, but also because others “copied” them and improved them.

But we forget how valuable bread recipes are. For one thing, recipes reduce uncertainty: thanks to them, bakers know that, barring a sudden disaster, bread will be ready for dinner. With this recipe, anyone can make bread without much imagination or talent. In the case of the authors, we don’t have any talent for bread baking, but you can still find Chabati’s recipes on the web, using the right amount of dough and using the methods written down by more imaginative and talented bakers. Eventually, the recipe became part of humanity’s heritage, passed down from generation to generation over thousands of years of history.

A recipe is an algorithm, and we have a preliminary definition of an algorithm: an algorithm is the process of solving a problem. We don’t have to invent a solution every time.

From this definition, we have been inventing, using and disseminating algorithms for cooking, carving, fishing, growing lentils and wheat, and so on, since the dawn of human history. [2]

Teacher Zha said: according to teacher Zha’s understanding, algorithm is to solve a specific need to provide a solution. In later study and work, it is common to use algorithms written by others and write my own business algorithm, so it is not necessary to understand it too abstract and lofty.

Sorting algorithm

Sorting algorithm both in life, or in the algorithm enlightenment play a very important role, and in the interview, big factory love is the idea of a variety of sorting algorithm or code handwriting.

The so-called sorting algorithm is to resort one or more groups of data according to the established pattern through a specific algorithm factor. The new sequence follows certain rules and reflects certain rules, so the processed data is easy to screen and calculate, and greatly improves the computational efficiency. For sorting, we first require it to have a certain stability, that is, when two identical elements appear in a sequence at the same time, after a certain sorting algorithm, their relative positions before and after the sorting will not change. In other words, even if two identical elements are sorted differently, they should not be confused. [3]

Sorting algorithm also has many kinds of solutions, common are: bubble sort, selection sort, insertion sort, quick sort, heap sort, merge sort, hill sort, radix sort and so on.

Next, Mr. Zha will introduce you to three kinds of sorting algorithms, which is also a supplement to our basic data structure. However, in this article, Mr. Zha will not introduce you to the time complexity and space complexity of the algorithm. It is only an introduction to the sorting idea and basic implementation.

Bubble sort

An overview of the

Bubble sort is one of the simplest sorting algorithms.

It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if the order is wrong (from largest to smallest, Z to A). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element column has been sorted.

Arises because the name of the algorithm, the smaller the element will slowly through the exchange of “float” to the top of the sequence (ascending or descending order), like carbon dioxide bubbles in carbonated beverages will eventually rise to the top (this is because of the tiny bubbles of carbon dioxide is lighter than water, so small bubbles can float upwards bit by bit.) , hence the name “bubble sort”. [4]

Sorting thought

Core idea: compare adjacent elements, and compare them in pairs.

  1. The two adjacent elements are compared, and after the comparison, the smaller elements are moved to the front, and the larger elements are moved to the back.
  2. After each round of comparison, the “largest element” is shifted to the end. In the next round of comparison, the “largest element” doesn’t need to participate in the comparison.
  3. Repeat the above steps, and after n-1 rounds of comparison, the sorting is complete. (N: indicates the number of elements to be compared.)

Code implementation

int[] arr = {9.7.8.6.2};
        
// Outer loop: n-1
for (int i = 0; i < arr.length - 1; i++) {
    // Inner loop: n-1-i
    // -1 is used to prevent array traversal: index out of bounds exception
    // -i is used to exclude the largest element of the previous round of comparison
    for (int j = 0; j < arr.length - 1 - i; j++) {
        // Compare adjacent elements in pairs
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp; }}}Copy the code

Selection sort

An overview of the

It is a simple and intuitive sorting algorithm.

It works by first picking the smallest (or largest) element from the data elements to be sorted, storing it at the beginning of the sequence, then finding the smallest (or largest) element from the remaining unsorted elements, and placing it at the end of the sorted sequence.

And so on until the total number of data elements to be sorted is zero. Selection sort is an unstable sort method. [5]

Sorting thought

Core idea: fight arena to find the minimum value train of thought.

  1. For the first comparison, the first element is assumed to be the smallest element.
  2. The first element is then compared in turn to all subsequent elements, and if the latter element is smaller than the first, the swap is performed.
  3. After each round of comparison, the “smallest element” is shifted to the “first element position”. In the next round of comparison, this “smallest element” doesn’t need to participate in the comparison anymore.
  4. Repeat the above steps, and after n-1 rounds of comparison, the sorting is complete. (N: indicates the number of elements to be compared.)

Code implementation

int[] arr = {9.7.8.6.2};
        
// Outer loop: n-1
for (int i = 0; i < arr.length - 1; i++) {
    // Inner loop: get the minimum
    // The initial value I + 1 is to eliminate the problem of comparing the first element with the second element.
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[i]) {
            inttemp = arr[j]; arr[j] = arr[i]; arr[i] = temp; }}}Copy the code

The teacher said: in the selection of sorting, including what we have learned in front of the fight for the maximum value, minimum value ideas, you can review.

Insertion sort

An overview of the

It is also commonly referred to as direct insertion sort. It is an efficient algorithm for sorting a small number of elements.

Insertion sort is one of the simplest sorting methods. Its basic idea is to insert a record into an ordered list that has been sorted, thus creating a new ordered list that increases the number of records by one. In the process of its implementation, the use of a double-layer loop, the outer loop to all elements except the first element, the inner loop to the ordered list in front of the current element to be inserted position search, and move. [6]

Sorting thought

Core idea: to do the insertion in the ordered sequence, and keep the order.

  1. The first element is treated as a sorted sequence and the rest as an unsorted sequence.

    {{a1}, {a2, a3, a4, ... , an}}

  2. Then insert the second element into the sorted array. That is, in the sorted sequence, search for the position that conforms to the ascending rule from the back to the front and insert it into the position.

    The new sequence becomes {{a1, a2}, {a3, A4… , an}}

  3. Repeat this step until the sorting is complete.

Code implementation

int[] arr = {9.7.8.6.2};
        
for (int i = 1; i < arr.length; i++) {
    for (int j = i; j > 0; j--) {
        // Find a position in the ordered array to insert, and keep the order.
        if (arr[j] < arr[j - 1]) {
            int temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp; }}}Copy the code

reference

[1] Baidu Baike. Algorithm [EB/OL]. baike.baidu.com/item/ algorithm. 2021.1.20

[2] Serge Abbot, Jill Dovic. Algorithm Times: From Mathematics to Life [M]. Posts and Telecommunications Press,2018:1-10.

[3] Li Mingda, HE Lili. China management informatization,2018,21(5):162-164.

[4] Baidu Baike. [EB/OL]. baike.baidu.com/item/ Bubble sort. 2021.1.20

[5]Ajay Kumar. Data Structure for C Programming: Firewall Media, 2004:268-270

[6] Baidu Baike. [EB/OL]. baike.baidu.com/item/ insert Sort. 2021.1.20

Afterword.

C: Ok, the introduction of sorting algorithm is over here, this homework please search wechat attention: check the teacher’s handout, and then reply to the sorting algorithm introduction homework can be.

In this article, we’ve taken a look at the three most familiar sorting algorithms that you can learn at this stage, but these algorithms alone give us a sense of the work of computer scientists.

They all have their own characteristics, their own subtleties, to play with them, we need to spend a lot of time.

Teacher Zha said: For the learning of technology, teacher Zha has always followed the following steps: With a simple demo to let it run first, and then learn it the most commonly used API and configuration can let yourself up, finally, on the basis of proficiency in the spare time reading the source to try to make myself to be able to see clearly its running mechanism, part of the cause of the problem, at the same time, draw lessons from these technology to enhance your own code level.

So in the teacher’s article, the early basic are small white, only interspersed with a very small amount of source research. Of course, such as the small white update, you still like, the late will not regularly dedicated to part of the technology of the source code analysis.