About the author: Su Yong, senior software engineer. This text is from: Hook Education
Data Structures and Algorithms in 300 minutes

Hello, I’m su Yong, your algorithm teacher. Welcome to today’s lesson. In the first two lessons, we have learned several complex data structures commonly used in interviews. They are the cornerstone of learning algorithms well. Only if we have a firm grasp of their properties, we will be able to play with ease in the following lessons.

Algorithm learning is actually a process of learning and improving thinking ability. No matter in the interview or in the actual work and life, we will meet some problems that we have never met before. Usually, we will consider them according to our existing experience, and we will list various solutions, discuss their feasibility and risks, and finally choose the best solution.

It’s the same way we learn algorithms. When the interviewer put forward a question that you have never seen, don’t panic, first think of the most intuitive method, although in most cases, it is not the best way, but it can help you get through, sort out the various steps to solve the problem, and then often, we need to solve the core is to optimize a step. For example, recall that we borrowed prefix trees in order to speed up string matching.

In addition, there are so many algorithms in the world that it is impossible for us to have enough time and energy to prepare one by one. Therefore, in the next five lessons, I will introduce some of the most frequently tested and core algorithms in the interview to you, hoping that you can learn and digest them well.

Data Structures and Algorithms in 300 Minutes

I’m sure you’re familiar with sorting algorithms, and you can list several different sorting algorithms, but you really need to be familiar with the following sorting algorithms in preparation for an interview:

  1. Basic sorting algorithm

Bubble Sort

Insertion Sort

  1. Sorting algorithms are often examined

Merge Sort

Quick Sort

Topological Sort

  1. Other sorting algorithms

Heap Sort

Bucket Sort

Bubble sort and insert sort are the most basic sorting algorithms. Don’t underestimate them because they are simple and straightforward. Interviewers sometimes like to use them to test your basics and see if you can quickly write bug-free code. The ideas of merge sort, quicksort, and topological sort are key to solving most sorting problems in interviews, and we will focus on them in this lesson. As to heap sort and bucket sort, to see if you have the time, especially the bucket sorting, in certain circumstances (such as know the range of all elements), it can solve the battle in linear time complexity, mastering the problem solving ideas can widen their thinking, in the interest of time, we conduct the thorough research to the right, they are here.

Let’s explore bubble sorting.

Bubble Sort

First, let’s look at the basic idea of bubble sort.

The basic idea

Given an array, we pour all the elements of the array into a pool, where they bubble to the surface, one by one, in order of size, by comparing them to each other. In each round, starting with the jumbled head of the array, two elements are compared and swapped until the largest or smallest element is placed at the end of the array, and the process is repeated until all the elements are in place.

As you can see, the process of comparing elements to each other is the core operation of bubble sorting. Let’s go through a problem to understand it better.

Data Structures and Algorithms in 300 Minutes

Sample analysis

Given an array [2, 1, 7, 9, 5, 8], sort from left to right and from smallest to largest. We can bubble from left to right, just move the larger numbers to the right.

First, the pointer points to the first number and compares the size of the first number and the second number. Since 2 is larger than 1, it is swapped in pairs [1, 2, 7, 9, 5, 8].

Next, the pointer moves forward one step and compares 2 and 7. Since 2 is smaller than 7, both remain fixed, [1, 2, 7, 9, 5, 8]. Seven is by far the largest number.

The needle continues to move forward, comparing 7 and 9, and since 7 is smaller than 9, both remain fixed, [1, 2, 7, 9, 5, 8]. Now, 9 becomes the largest number.

Further down the line, compare 9 and 5. It is obvious that 9 is larger than 5. Swap them [1, 2, 7, 5, 9, 8].

Finally, compare 9 and 8, 9 being larger than 8, and switch their positions, [1, 2, 7, 5, 8, 9]. After the first pairwise comparison, the largest number, 9, bubbled to the bottom of the array.

For the second round of comparison, we repoint the pointer to the first element, repeat the above operation, and finally the array becomes: [1, 2, 5, 7, 8, 9].

You can see that the array is already sorted. But how do we let the algorithm know? We can do a new round of comparison and see if there was a p2-p2 swap during the last round of comparison, and if neither swap happened, then the array is sorted.

Code sample

Let’s look at the bubble sort code.

void sort(int[] nums) {
  boolean hasChange = true;
 
  for (int i = 0; i < nums.length - 1 && hasChange; i++) {
    hasChange = false;
 
  for (int j = 0; j < nums.length - 1 - i; j++) {
  if (nums[j] > nums[j + 1]) {
        swap(nums, j, j + 1);
        hasChange = true; }}}}Copy the code


First, we define a Boolean variable hasChange, which is used to mark whether a swap occurred in each iteration.

  1. At the beginning of each iteration, set hasChange to false.
  2. Next, do a pairwise comparison, and if you find that the current number is larger than the next one, swap the two numbers and note that a swap occurred.
  3. Keep swapping in pairs until the largest number is placed at the end of the array in this round.

Algorithm analysis

Let’s analyze the space and time complexity of the bubble sort algorithm. Let’s say the number of elements in the array is n, and since we’re directly swapping elements in the given array in the whole sorting process, the space complexity is ORDER 1. For time complexity, let’s look at the following cases:

  1. The given array is sorted in order

In this case, we only need to do n minus one comparisons, with zero p2-p2 swaps and O(n) time complexity, which is the best case.

  1. The given array is sorted in reverse order

In this case, we need n(n-1) / 2 comparisons, O(n^2) in time, which is the worst case.

  1. The given array is messy

In this case, the average time is O(n^2).

So, bubble sort is O(n^2) in time, but it’s a stable sorting algorithm, which means that if there are two equal numbers in the array, then the relative positions of the two equal numbers remain the same before and after sorting.

Next time, we’re going to delve into recursive algorithms and backtracking algorithms, which are the most likely to show up in algorithm interviews. Ok, see you next time! Pay attention to my public number: IT technology thinking, reply: 123, you can get free big factory interview real questions oh ~

Data Structures and Algorithms in 300 Minutes

Copyright notice: The copyright of this article belongs to Pull hook education and the columnist. Any media, website or individual shall not be reproduced, linked, reposted or otherwise copied and published/published without the authorization of this agreement, the offender shall be corrected.