This is the 8th day of my participation in Gwen Challenge

Algorithm learning is actually a process of improving thinking ability. Whether it is learning algorithm, or in the interview or actual work, life, we will meet some problems that we have never met before. The solution is similar: first refine the most intuitive solution and then optimize one of the steps.

Basic sorting algorithm

Bubble Sort

Insertion Sort

Sorting algorithms are often examined

Merge Sort

Quick Sort

Topological Sort

Other sorting algorithms

Heap Sort

Bucket Sort

Bubble sort and insert sort are the basics, and interviewers sometimes like to use them to gauge your basics and see if you can quickly write bug-free code.

The ideas of merge sort, quick sort and topological sort are the key to solve most of the sorting problems.

Heap sorting and bucket sorting are not studied in depth in this article, but must be looked at if you have time, especially bucket sorting, in certain situations (such as knowing the range of all elements appear), can solve battles in linear time complexity, grasp the idea of its solution can broaden the idea of solving problems.

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.

For each round, starting with the jumbled head of the array, each of the two elements is sized 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. The core operation is comparing elements to each other.

Analyze a given array [2, 1, 7, 9, 5, 8] and sort it from left to right and from smallest to largest.

You’re bubbling from left to right, and you can just move the larger number 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.

We then do a second round of comparison, reroute the pointer to the first element, and repeat. Finally, the array becomes [1, 2, 5, 7, 8, 9].

In a new round of comparison, determine whether pwise swapping occurred during the previous round of comparison. If neither swap occurred, the array is sorted.

void sort(int[] nums) {
    // Define a Boolean variable hasChange to indicate whether a swap occurred in each iteration
    boolean hasChange = true; 

    // Set hasChange to false at the beginning of each iteration
    for (int i = 0; i < nums.length - 1 && hasChange; i++) {
        hasChange = false;

        If the current number is greater than the next one, swap the two numbers and record that the swap occurred
        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

The algorithm analyzes the space complexity by assuming that the number of elements in the array is N. Since in the whole sorting process, we are directly swapping elements in the given array in pairs, the space complexity is O(1).

Time complexity

  1. The given array is sorted in order

In this case, we only need to perform n−1 comparisons, with pairwise switching of 0 and time complexity O(n). That’s the best case scenario.

  1. The given array is sorted in reverse order

In this case, we need n(n-1)/2 comparisons, O(n2). That’s the worst-case scenario.

  1. The given array is messy

In this case, the average time complexity is O(n2).

Thus, the time complexity of bubble sort is O(n2). It is a stable sorting algorithm. (Stable means that if two equal numbers are in an array, their relative positions remain the same before and after sorting.)

Insertion Sort

The basic idea is to constantly insert unsorted numbers into sorted parts.

Features In bubble sort, after each round of sorting, the number at the back of the array is sorted; In the case of insert sort, after each round of sorting, the numbers at the front of the array are sorted.

Insert sort on arrays [2, 1, 7, 9, 5, 8].

The left part is the sorted part, and the right part is the unsorted part. At first, the sorted part on the left has only the first element, 2. Next, we take the elements on the right, one by one, and put them on the left.

​

  • Let’s look at 1 first. Since 1 is smaller than 2, we need to insert 1 in front of 2. It’s easy to switch places in pairs, [1, 2, 7, 9, 5, 8].

  • Then, we insert 7 into the left-hand portion, since 7 is already larger than 2, indicating that it is by far the largest element, holding position, [1, 2, 7, 9, 5, 8].

  • Similarly, 9 does not need to change position [1, 2, 7, 9, 5, 8].

  • Next, how to insert the 5 into the right place. First compare 5 and 9, since 5 is smaller than 9, pairwise swap, [1, 2, 7, 5, 9, 8], continue, since 5 is smaller than 7, pairwise swap, [1, 2, 5, 7, 9, 8], and finally, since 5 is larger than 2, the round ends.

  • The final number is 8. Since 8 is smaller than 9, switch pairs, [1, 2, 5, 7, 8, 9], and compare 7 and 8. 8 is larger than 7. At this point, insert sort is done.

void sort(int[] nums) {
    // Take the first element of the array as if it were already sorted, and start with the second element, I, starting at 1
    for (int i = 1, j, current; i < nums.length; i++) {
        // Start the loop with the current value to which I is pointing
        current = nums[i];

        If j is larger than current, the number moves to the right one bit
        for (j = i - 1; j >= 0 && nums[j] > current; j--) {
            nums[j + 1] = nums[j];
            }
    
        // When the inner loop ends, j+1 points to the position where the current value is inserted
        nums[j + 1] = current; }}Copy the code

The algorithm analyzes the space complexity by assuming that the number of elements in the array is N, and the space complexity is O(1), since the whole sorting process is to swap the elements in pairs directly in the given array.

Time complexity

  1. The given array is sorted in order

It only takes n minus one comparisons, and the number of pings is zero, and the time is O(n). That’s the best case scenario.

  1. The given array is sorted in reverse order

In this case, we need n(n-1)/2 comparisons, O(n2). That’s the worst-case scenario.

  1. The given array is messy

In this case, the average time complexity is O(n2).

It can be seen that, like bubble sort, the time complexity of insertion sort is O(n2), and it is also a stable sorting algorithm.

LeetCode 第 147, insert sort a linked list.

Merge Sort

The core of the basic idea is divide and conquer, which is to divide a complex problem into two or more identical or similar sub-problems, and then divide the sub-problems into smaller sub-problems, until the sub-problems can be solved simply and directly. The solution of the original problem is the combination of the solutions of the sub-problems. Merge sort embodies the idea of divide and conquer thoroughly.

The implementation starts by dividing the array into two subarrays in the middle and continues to recursively divide the subarray into smaller subarrays until there is only one element in the subarray.

Sorting is done by merging two elements in order of size, then recursively merging the subarrays in order of return, until the entire array is sorted.

The code implementation for the body function is as follows.

void sort(int[] nums) {
    // Take the first element of the array as if it were already sorted, and start with the second element, I, starting at 1
    for (int i = 1, j, current; i < nums.length; i++) {
        // Start the loop with the current value to which I is pointing
        current = nums[i];

        If j is larger than current, the number moves to the right one bit
        for (j = i - 1; j >= 0 && nums[j] > current; j--) {
            nums[j + 1] = nums[j];
            }
    
        // When the inner loop ends, j+1 points to the position where the current value is inserted
        nums[j + 1] = current; }}Copy the code

The code for the merge operation is as follows.

void merge(int[] nums, int lo, int mid, int hi) {
    // Copy the original array
    int[] copy = nums.clone();
  
    // Define a k pointer to indicate the starting position of the original array, I to indicate the starting position of the left half, and j to indicate the starting position of the right half
    int k = lo, i = lo, j = mid + 1;
  
    while (k <= hi) {
        if (i > mid) {
            nums[k++] = copy[j++];
        } else if (j > hi) {
          nums[k++] = copy[i++];
        } else if (copy[j] < copy[i]) {
          nums[k++] = copy[j++];
        } else{ nums[k++] = copy[i++]; }}}Copy the code

Among them, the While statement comparison, a total of four cases may occur.

  • I’m done with everything on the left, and I’m left with everything on the right, so I just copy everything on the right.

  • I’m done with everything on the right, and I’m left with everything on the left, so I just copy everything on the left.

  • The number on the right is less than the number on the left. Copy the number on the right to the appropriate position and move the j pointer forward one bit.

  • The number on the left is less than the number on the right. Copy the number on the left to the appropriate position and move the I pointer one bit forward.

Sample analysis

Example: Sort arrays [2, 1, 7, 9, 5, 8] using merge sort algorithm.

Their thinking

First, the array is continuously shred until each subarray contains only one element.

The subarrays are then merged recursively in size order, similar to the forward traversal in a binary tree.

  • Merge [2] and [1] into [1, 2].

  • Merge the subarrays [1, 2] and [7].

  • On the right, merge [9] and [5].

  • Then combine [5, 9] and [8].

  • Finally, merge [1, 2, 7] and [5, 8, 9] into [1, 2, 5, 8, 9], and you can sort the entire array.

The steps for merging arrays [1, 2, 7] and [5, 8, 9] are as follows.

​

  • The arrays [1, 2, 7] are represented by L and [5, 8, 9] by R.

  • When merging, allocate a new array T to hold the result. The size of the array should be the sum of the length of the two subarrays

  • Then the subscripts I, j, and k point to the starting point of each array.

  • Next, compare the elements L[I] and R[j] pointed to by the subscripts I and j, and place them in order of magnitude where the subscripts K point, 1 is less than 5.

  • Moving I and K, continuing to compare L[I] and R[j], 2 is less than 5.

  • I and K keep moving forward. 5 is less than 7.

  • Moving j and K, continuing to compare L[I] and R[j], 7 is less than 8.

  • At this point, the left array has been processed, and the remaining elements of the right array are simply added to the resulting array.

The prerequisite for a merge to succeed is that both subarrays have been sorted separately. Space complexity Since merging n elements requires allocating an additional array of size N, the space of the array is freed once the merging is complete, so the space complexity of the algorithm is O(n). Merge sort is also a stable sort algorithm.

Time – complexity merging algorithm is a continuous recursive process.

Example: the number of elements in the array is n, the time complexity is T(n) function.

Solution: Divide the problem of size N into two subproblems of size N /2 respectively. The time complexity of each subproblem is T(n/2), so the complexity of the two subproblems is 2×T(n/2). When both subproblems are solved, that is, both subarrays are sorted, you have to merge them, there are n elements, and you have to compare them at most n minus 1 times, so the merge is O(n). Thus we get the recursive complexity formula: T(n) = 2×T(n/2) + O(n).

For the solution of the formula, a problem of size N is continuously decomposed into a problem of size N /2, until it is decomposed into a problem of size 1. If n is equal to 2, you only divide it once; If n is 4, you have to do it twice. The numbers here are classified by changes in size.

Similarly, for a problem of size N, a total of log(n) layers of size segmentation are performed. At each level, we’re going to merge, and the elements involved are really all of the elements in the array, so the merge complexity at each level is ORDER n, so the overall complexity is order N logn.

Suggestion: merge algorithm idea is very important, which two ordered array merge operation, in many interview questions are useful, I suggest you must practice this algorithm.

Quick Sort

Basic idea Quicksort also uses the idea of divide-and-conquer.

The implementation filters the original array into smaller and larger subarrays, and then sorts the two subarrays recursively.

Example: Line up all the students in the class in order of height.

Solution: The teacher randomly selected student A and asked all the other students to compare their height with A. Those shorter than A stood on the left of A, and those taller than A stood on the right of A. Next, the teacher selects students B and C from the left and right respectively, and then continuously selects and arranges them.

Choosing A reference value (that is, students A, B, C, etc.) is crucial when dividing into smaller and larger subarrays.

Sort the array [2, 1, 7, 9, 5, 8].

Their thinking

According to the idea of quicksort, the array is filtered into smaller and larger subarrays.

Pick a random number from the array as a reference value, such as 7, and the original array is split into two subarrays. Note: Quicksort performs swaps directly in the original array, so when the subarray is split, the arrangement in the original array is changed.

Next, select 2 as the base value in the smaller subarray and 8 as the base value in the larger subarray, and continue to split the subarray.

Continue to divide the subarray with more than 1 elements. When all the subarrays have 1 elements, the original array is sorted.

The body function code is as follows.

void sort(int[] nums, int lo, int hi) {
    if (lo >= hi) return; // Check if there is only one element left
    
    // Use partition to find a random reference point
    int p = partition(nums, lo, hi);
    
    // Sort the numbers on the left and right halves of the datum recursively
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}
Copy the code

The following code implements the partition function to get the reference value.

void sort(int[] nums, int lo, int hi) {
    if (lo >= hi) return; // Check if there is only one element left
    
    // Use partition to find a random reference point
    int p = partition(nums, lo, hi);
    
    // Sort the numbers on the left and right halves of the datum recursively
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}
Copy the code

Time complexity

  1. Best case: The selected reference value is the middle of the current subarray.

Such segmentation can ensure that a problem of size N can be evenly decomposed into two sub-problems of size N /2 (merge sort also adopts the same partition method), and the time complexity is: T(n) = 2×T(n/2) + O(n).

When a problem of size N is decomposed into two subproblems of n/2, the complexity is O(n) after n-1 comparison with the reference value. Obviously, in the optimal case, quicksort is also O(nlogn).

  1. Worst case: The reference value selects the maximum or minimum value in the subarray

Each time, the subarray is divided into two smaller subarrays, one of which is 1 in length and the other is only 1 less in length than the atomic array.

Example: For an array, the base values for each pick are 9, 8, 7, 5, 2.

Solution: The partitioning process is similar to bubble sorting.

The algorithm complexity is O(n2).

Tip: You can avoid the worst by randomly selecting the base values.

Space complexity and merge sort, quick sort, in the process of each recursive only need to open up the O (1) the storage space to do exchange operations to achieve an array of modified directly, and because times as recursive logn, so its overall space complexity depending on the number of pressure stack completely, so it is the space complexity of O (logn).

Example: LeetCode problem 215, given an unsorted array, asks to find the KTH largest number.

Solution 1: Sort the array directly and get the result.

Solution 2: Quicksort.

Randomly select a reference value each time, divide the array into the smaller half and the larger half, and then check whether the subscript of the last reference value is K. The algorithm complexity only needs O(n).

Topological Sort

The basic idea is different from the previous sorting, topological sorting is no longer a simple array, but to study the properties between vertices and vertex lines in graph theory. Topological sort is to sort these vertices according to their contiguous properties.

To achieve topological sort, there are several prerequisites:

  • A graph must be directed

  • There are no rings in the diagram

Topological sorting is generally used to sort out tasks with dependencies.

For example, suppose there are three courses A, B and C. If you want to learn course C, you must finish course B first. If you want to learn course B, you also need to learn course A first.

The implementation abstracts the problem into a Directed Acyclic Graph (DAG) that defines what are the vertices of the Graph and how they relate to each other.

You can use breadth-first search or depth-first search for topological sorting.

There is a student who wants to complete the credits of 5 courses, which are denoted as 1, 2, 3, 4, and 5 respectively. It is known that the requirements for these courses are as follows:

  • Lectures 2 and 4 are dependent on lectures 1

  • Course 3 depends on course 2 and Course 4

  • Course 4 depends on course 1 and 2

  • Course 5 depends on course 3 and 4

In what order should the student take the five courses?

The five courses can be regarded as five vertices in a graph, which are connected by directed line segments according to their mutual relations, and the following directed graph can be obtained.

The first thing you can see is that there are no cycles in this digraph, and no matter what vertex you start at, you never get back to that vertex. Also, there are no islands in the graph, so we can sort it topologically.

The way to do this is, at the beginning, to count each vertex for its own precursor (that is, the degree of entry) : 1(0), 2(1), 3(2), 4(2), 5(2).

​

  • Select one of the vertices that has no precursor (i.e. an entry degree of 0), in this case vertex 1 is the point we are looking for, and print it as the result. Update the entry table of vertices by deleting this vertex and all directed edges that start with it.

  • Next, vertex 2 is the next vertex without a precursor, outputs vertex 2, and removes the directed edge with it as the starting point, and updates the degree table.

  • Again, vertex 4 becomes a vertex without a precursor, outputs vertex 4, and removes its directed edges with vertices 3 and 5.

  • Then, vertex 3 has no precursor, outputs it, and removes its directed edge with 5.

  • Finally, vertex 5 has no precursor, outputs it, and the final result is: 1,2,4,3,5.

In general, a directed acyclic graph can have one or more topologically ordered sequences.

The breadth-first search method is used to traverse the structure of the graph. In the process of constructing this graph, a link matrix ADJ is used to represent the structure of this graph, and an array of indegree is used to count the entry degree of each vertex, focusing on how to achieve topological sorting.

void sort(a) {
    Queue<Integer> q = new LinkedList(); // define a queue q

    // Add all vertices with degree 0 to queue Q
    for (int v = 0; v < V; v++) {
        if (indegree[v] == 0) q.add(v);
    }

    // loop until the queue is empty
    while(! q.isEmpty()) {int v = q.poll();
        // In each loop, the vertex from the queue is the smallest vertex sorted by the number of entries
        print(v);

        // Subtract the degree of entry of the other vertices connected to this vertex by 1. If the degree of entry of that vertex becomes 0, add it to the end of the queue
        for (int u = 0; u < adj[v].length; u++) {
            if (--indegree[u] == 0) { q.add(u); }}}}Copy the code

Time complexity

It takes O(n) time to count the entry degree of vertices, and it also takes O(n) time for each vertex to be traversed once, so the time complexity of topological sorting is O(n).

Suggestion: Use depth-first search method to achieve topological sorting of this problem.

Conclusion This paper mainly reviews the sorting algorithm often tested in the interview, the most important content is merge sort and quick sort. In addition to a good understanding of their thinking, you must also be able to write bug-free code, so it is recommended to do more of the classic problems in LeetCode.