Understand basic sorting algorithms

The last article wrote about the basic knowledge of Java inner class, interested friends can go to see: understand Java inner class; The content of this article is the recent learning of the algorithm related knowledge of the basic sorting algorithm, sorting algorithm is also a frequent interview, in fact, is the most basic knowledge of the algorithm. Since Android is not used much in development, it is easy to forget, but it is also required to consolidate basic algorithms and data structures for advanced engineers.

Basic sorting algorithm according to the degree of difficulty can be divided into: bubble sort, select sort, insert sort, merge sort, select sort. This article will also explain the central idea of each of the five sorting algorithms and their Java implementation.

Bubble sort

Bubble sort is probably the first sorting algorithm that we have come into contact with in computer courses, and it is also an entry-level sorting algorithm.

Bubble sort is simple but it’s actually very inefficient for large n orders of magnitude. So this kind of sorting algorithm is seldom used in actual production. Let’s take a look at the specific implementation of this algorithm:

Bubbling sort algorithm principle:

  1. Compare adjacent elements. If the first one is bigger than the second, swap them both.
  2. Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number.
  3. Repeat this step for all elements except the last one.
  4. Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.

A comparison process is shown in the figure below.

Bubble sort Java code implementation:

Private static void BubbleSort(int[] arr, int n) {private static void BubbleSort(int[] arr, int n) {for (int i = 0; i < n - 1; i++) {
        for (int j = 1; j < n - i; j++) {
            if(arR [j-1] > arR [J]) {int temp = arr[J]; arr[j] = arr[j - 1]; arr[j - 1] = temp; }}}}Copy the code

Time space complexity and algorithm stability analysis of bubble sort

For an array of length N, bubble sort requires n(n-1)/2 comparisons, and in the worst case, if the array itself is in reverse order, it requires n(n-1)/2 swaps, so

The average time complexity of bubble sort algorithm is O(n²). The space complexity is O(1).

Imagine this: if two adjacent elements are equal, there is no swap operation, that is, the order of equal elements does not change. If two equal elements are not adjacent, then even if the two elements are adjacent by the previous pair swap, they will not change their position, so the order of the same elements will not change.

So bubble sort is a stable sort algorithm. So bubble sort is stable sort. This is the definition of algorithm stability:

Stability of sorting algorithm: generally speaking, it is able to ensure that the order of the first two equal data in the sequence is the same as the order of the two after sorting.

Bubble sort summary:

  1. The average time complexity of bubble sort algorithm is O(n²).
  2. The space complexity is O(1).
  3. Bubble sort is stable sort.

Selection sort

Selection sort is another simple sorting algorithm. Selected-sort is called selected-sort because you find the smallest element in a traversal, and you put it at the top of the array. When we sort, we’re always looking for the smallest element in the remaining array, so it’s called selective sort.

The idea of selection sorting

The idea of selection sort is also simple:

  1. From the sequence to be sorted, find the element with the smallest keyword; The first element is assumed to be the smallest
  2. If the smallest element is not the first element in the sequence to be sorted, swap it with the first element;
  3. From the remaining n-1 elements, find the element with the smallest keyword, and repeat 1 or 2 steps until the sorting is complete.

Schematic diagram:

Select sort Java code implementation:

public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int minIndex = i;
            // forLoop through all the numbers after I to find the least worth index in the remaining arrayfor (int j = i + 1; j < n; j++) {
                if(arr[j]< arr[minIndex]) { minIndex = j; } } swap(arr, i, minIndex); Private static void swap(int[] arr, int I, int j) {int temp = arr[I]; private static void swap(int[] arr, int I, int j); arr[i] = arr[j]; arr[j] = temp; }Copy the code

Analysis of time space complexity and algorithm stability of selective sorting

As you can see from the Java code above, we didn’t create any extra space except for swapping elements, so the extra space complexity is O(1).

In terms of time complexity, selecting sort order bubble sort also requires traversal n(n-1)/2 times, but compared with bubble sort, each traversal only needs to swap elements once, which is a certain optimization for computer execution. But selection sort is really slow, because even an ordered array requires n(n-1)/2 comparisons, so it’s O(n ^ 2).

Even if n(n-1)/2 comparisons are performed anyway, selection sorting is still an unstable sorting algorithm. Let’s take an example like sequence 5, 8, 5, 2, 9. We know that the first selection of element 5 will swap with element 2, and the relative order of the two 5’s in the original sequence will be broken.

Selection sort summary:

  1. The average time complexity of the selection sorting algorithm is O(n²).
  2. The selection sort space complexity is O(1).
  3. Select sort as unstable sort.

Insertion sort

For insertion sort, most of the information is the use of poker sorting as an example to introduce, we play cards are a touch of the card, did not touch a card will be compared with all the cards in the hand to choose the appropriate position to insert this card, this is the central idea of direct insertion sort, we first look at the GIF:

I believe you probably know the idea of insertion sort after watching the GIF. So let’s talk about the idea of insertion sort.

Insert the idea of sorting

  1. Start with the first element, which can be considered sorted
  2. Takes the next element and scans back to front in the sorted element sequence
  3. If the element (sorted) is larger than the new element, move the element to the next position
  4. Repeat step 3 until you find a place where the sorted element is less than or equal to the new element
  5. After inserting the new element into the location
  6. Repeat steps 2 to 5

Java implementation of insert sort:

Let’s look at the most basic implementation:

    public static void sort(int[] arr) {
        int n = arr.length;
        for(int i = 0; i < n; I ++) {// The inner loop compares the values of I and all the preceding elements, and swaps them if the value indicated by the j index is less than j-1for(int j = i; j > 0 && arr[j-1] > arr[j]; j--){ swap(arr,j-1,j); }}}Copy the code

In the implementation of the algorithm above, every time we find where I should be in the array, we have to swap the current element with the last element, and we know that swapping takes more time than assigning, because each swap requires three assignments. We think when we play poker no picked up a card one by one move forward on its location, it should be take out this card, find the location in them (evil) suddenly, in fact we will be back after the position of brand in a one place, so whether in Java code can realize? The answer is definitely yes:

   public static void sort(int[] arr) {
        int n = arr.length;
        for(int i = 0; i < n; Int e = arr[I]; int e = arr[I]; // Find the right place for itfor(int j = i; j > 0 && arr[j-1] > arr[j]; j--){ arr[j]= arr[j-1]; } // arr[j] >= arr[j-1] arr[j] = e; }}Copy the code

Time complexity and space complexity analysis of insertion sort

The time complexity and the space complexity of inserts, as you can see from the code, is the same as selection and bubbling and it’s O(n ^ 2) time complexity, but traversal is the same n, N-1, n-2… One, becomes one, two, three… N. You end up with n times n minus 1 over 2.

For stability, insertion sort, like bubbling, does not change the order between elements. If an equal element is encountered, the element to be inserted is placed after the equal element. Therefore, the order of equal elements does not change, and the order out of the original unordered sequence is still the order after sorting, so insertion sort is stable.

Insert sort (arr[J-1] > arr[j]) is useful because it can terminate inner comparisons early. Therefore, for some NlogN level algorithms, the following merge and fast are of this level, the algorithm can be optimized with the insertion algorithm for n < a certain level (array.sort uses 47), and for nearly ordered arrays, the early termination method is more advantageous.

Insert sort summary:

  1. The average time complexity of insertion sort algorithm is O(n²).
  2. The insertion sort space complexity is O(1).
  3. Insert sort is stable sort.
  4. Insertion sort is more efficient for nearly ordered arrays and can be used to optimize advanced sorting algorithms

Merge sort

Now let’s look at an NlogN sorting algorithm, merge algorithm. The merge algorithm, as its name suggests, uses merge to sort:

We can always split an array in half, and then we can split it in four until we only have two elements in each group, which is kind of a recursive process, and then sort the two elements, and then sort the two elements in a group. Until all the elements are sorted. Again, let’s look at the GIF below.

The idea of merging algorithms

In fact, merge algorithm can be divided into recursive method and iterative method (from the bottom up merge), the two implementation of the minimum set of merge operation idea is the same, the difference lies in how to divide the array, let’s first introduce the algorithm’s most basic operation:

  1. Apply for a space that is the sum of two sorted sequences and is used to store the combined sequence
  2. Sets two Pointers, starting at the start of two sorted sequences
  3. Compare the elements to which the two Pointers point, place the smaller element into the merge space, and move the pointer to the next position
  4. Repeat step 3 until a pointer reaches the end of the sequence
  5. Copies all remaining elements of the other sequence directly to the end of the merged sequence

If we merge the arr[l…r] part of an array, we can divide the array into two parts: arr[l…mid] and ARr [mid+1…r]. Note that the two parts may not have the same length. Because when you divide an array of cardinals you always get a part of length 1 and a part of length 2 to merge.

So we code according to the above ideas:

Java implementation of merge sort:

Private static void merge(int[] arr, int l, int mid, int l, int mid) Int r = new int[r-l + 1]; int r = new int[r-l + 1];for (int i = l; i <= r; i++) {
            aux[i - l] = arr[i];
        }
        
        int i = l;
        int j = mid + 1;

        for (int k = l; k <= r; k++) {
            if(I > mid) {arr[k] = aux[j-l]; j++; }else ifArr [k] = aux[i-l]; (j > r) {arr[k] = aux[i-l]; i++; }else if(aux[i-l] < aux[j-l]) {arr[k] = aux[i-l]; i++; }else{arr[k] = aux[j-l]; j++; }}}Copy the code

I believe that you have understood the merging algorithm with the previous GIF and the above algorithm implementation, if you feel confused, you can try to take an array on paper to perform the merging process, I believe you will understand. That’s just the core of the algorithm, so how do we sort the entire array? As mentioned above, there are two methods, one is recursive partition method, the other is iterative traversal method (from bottom to top), so let’s start to see the recursive implementation:

Private static void mergeSort(int[] arr, private static void mergeSort(int[] arr, int l, int r) {if (l >= r) {
            return; Int mid = (l + r) / 2; // mergeSort(arr, L, mid); mergeSort(arr, mid + 1, r); // Check if the array is in order. If so, proceed to the next mergeif (arr[mid] <= arr[mid + 1]) {
            return; } // Merge (arr, l, mid, r); }Copy the code

If you don’t understand the recursive process, you can use the following diagram to understand it:

We merge to the left half, of course, to the left of the Level3 bottom also is the first of eight | 6, and then merge to the right after the completion of recursion Finally is 8 June 2 3 | 1 5 July 4 to merge.

For iterative implement merge actually and recursive implementation is different, the iteration time we is an element of an array can be divided into a, then once every two merge, the second time we will every two points a set of array, two of the merge, know the packet size equals to merge the array length, the first local sorting, gradually expand to the global order

Private static void mergeSortBU(Integer[] arr,) private static void mergeSortBU(Integer[] arr, Int n) {//sz = 1: [0] [1] {//sz = 1: [0] [1] {//sz = 1: [0] [1]... //sz = 2: [0,1] [2.3]... //sz = 4 : [0..3] [4...7] ...for(int sz = 1; sz <= n; Sz += sz) {arr[I, I +sz-1] arr[I +sz, I +sz+sz-1]; Because each merge merges two sZ-length portions of an arrayfor(int i = 0; i + sz < n; i += sz + sz) { merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1)); }}}Copy the code

So let’s say that the first time we have a merge of sz equals 1 that’s I equals 0, I equals 1 and the next time we have a merge of I equals 2, I equals 3 and so the inner loop I should be incrementing by two sz at a time in order to keep the corner markers out of bounds and keep the right half of the merge alive so I plus Math.min(I + sz + sz-1, n-1); Please refer to the picture below:

Time complexity and space complexity analysis of merge sort

There’s actually a recursive formula for the time complexity of merge sort, but simply given an array length of N, then we have logN partitions, and we end up with constant level merge, and we add up the merge times of all the layers and we get an NlogN, If you want to see the time complexity of merge sort, you can turn left to merge sort and its time complexity analysis, so I’m not going to go into this too much.

For the space complexity, we can see from the implementation of the algorithm that we apply for a temporary array of length N to merge so the space complexity is O(N);

And since aux[i-L] = AUX [j-L] does not exchange positions in the sorting process and directly obtains the first assignment of the preceding element, the algorithm is stable.

** Merge sort summary: **

  1. The average time complexity of merge sort algorithm is O(nlog(n)).
  2. Merge sort space is O(n).
  3. Merge sort is stable sort.
  4. for

Quick sort

Quicksort is the most widely used sort algorithm and is famous for its speed. Quicksort, like merge sort, is divide-and-conquer. The basic idea of divide-and-conquer is to decompose the original problem into several smaller sub-problems with similar structure to the original problem. Solve these subproblems recursively, and then combine the solutions of these subproblems into solutions of the original problem. We just have to focus on how to solve the smallest problem, and how to recurse to get the right algorithm. Quicksort can be divided into: single-path quicksort, double-path quicksort, three-path quicksort, the difference between them is to select a few Pointers to traverse the array and we’ll explain it in turn.

The idea of single-path fast algorithm:

First we take a number in the array, and we put it in a position where everything to the left of that position is less than that number, and everything to the right of that position is greater than that number.

  1. Suppose the array is arr[l…r] Suppose the specified value is the first element of the array int v = arr[l], and suppose j is marked with the last element less than v, that is, arr[j+1] > v. Arr [L +1… j] < v, ARr [j+1, I) >= v, as shown in the figure above.

  2. Let’s say that the element we’re looking at is e, e >= v and we just leave it there and go i++ to the next element,

  3. When e

  4. After the last element is examined, we can talk about arr[l] and arr[j] and just switch places.

  5. After the completion of the above traversal, arr[L +1… j] < v, arr[j+1, I) >= v is satisfied, then we only need to recursively investigate arr[L +1… j] and arr[j+1,r].

Java implementation of single-way quicksort:

 private static void quickSort(int[] arr, int l, int r) {

        if (l >= r) {
            return; Int p = partition(arr, l, r); quickSort(arr, l, p - 1); quickSort(arr, p + 1, r); } private static int partition(Integer[] arr, int l, int r) {private static int partition(Integer[] arr, int l, int r) { 1/n int randomNum = (int) (math.random () * (r-l + 1) + l); swap(arr, l, randomNum); int v = arr[l]; int j = l;for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                swap(arr, j + 1, i);
                j++;
            }
        }
        swap(arr, l, j);
        return j;
    }

    private static void swap( int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
Copy the code

Why in the above algorithm selected the current sort compare a random element in an array, suppose we’re on investigation of arrays sort has to have good, then we recursive tree will be the depth of the extension to the right N, this kind of situation that we don’t want to see, if we take in every partition randomly from an array a number, So if this is the smallest element in the current sorted array and the probability is 1 over n then the probability of picking the smallest element every time is very low.

The idea of double-path quicksort algorithm:

  1. As with single-path, double-path quicksort selects the first element of the array as the flag bit (randomly selected).

  2. Double-path quicksort requires two Pointers, I and j to l+1 and r, and then both of them are traversed through the middle of the array at the same time. Arr (j….r] >= v so we can initialize I = l+1 to ensure that the left interval is initially empty, and j = r to ensure that the right space is empty

  3. If I <= r and arr[I] <= v, I ++ is ok. When arr[I] > v, it means that the value of I is greater than the value of v and can wait for the value of j marker. When arr[I] is less than v, it’s not supposed to be there,

  4. So once you have the indices of I and j you have to decide if you’re at the end of the cycle, if I is already greater than j.

  5. Otherwise you would have said I and J swap places, and then I ++ j– keep going

  6. Arr [j] is the last element less than v and arr[I] is the first element greater than v. Therefore, j should be the position of v in the array. Therefore, arr[l] and arr[j] should be swapped after traversal.

Java implementation of double-way quicksort:

 private static void quickSort(int[] arr, int l, int r) {

        if (l >= r) {
            return; Int p = partition(arr, l, r); partition(arr, l, r); quickSort(arr, l, p - 1); quickSort(arr, p + 1, r); } private static int partition(int[] arr, int l, int r) {private static int partition(int[] arr, int l, int r) { Int randomNum = (int) (math.random () * (r-l + 1) + l); swap(arr, l, randomNum); int v = arr[l]; int i = l + 1; int j = r;while (true) {

            while (i <= r && arr[i] <= v) i++;
            while (j >= l + 1 && arr[j] >= v) j--;

            if (i > j) break; swap(arr, i, j); i++; j--; } // swap(arr, l, j) swap(arr, l, j);return j;
    }
Copy the code

Dual-path quicksort is the most commonly used implementation of quicksort, which is the internal principle of Java’s sort arrays.sort () collections.sort () for basic data types.

Three-way quicksort

In the above two algorithms, we find that redundant swap processing is always done for the same worth processing as the flag bit. If we can divide the array into > = < three parts, the efficiency may be improved. As shown below:

  1. We divide the array into arr[l+1…lt]

    v where lt refers to the element before the last

    v, and I is the element under investigation
    ,>

  2. If you define an initial value, you can still make sure that all three of these are empty when you start int lt = l; int gt = r + 1; int i = l + 1;

  3. When e > v we need to swap arr[I] with arr[GT-1] and expand > v by one element gt– but the I pointer doesn’t need to operate at this point because the swapped number hasn’t been evaluated yet.

  4. When e is equal to v I ++ let’s go to the next one

  5. When e < v we need to swap arr[I] with arr[lt+1]

  6. At the end of the loop lt is the last element less than v so finally we need to swap arr[l] with arr[lt].

  7. Finally, arr[l…lt-1] and ARr [gt…r] are sorted recursively to get the correct result.

See Figure 2 below

Three way quick sort Java code implementation:


    private static void quickSort3(int[] num, int length) {
        quickSort(num, 0, length - 1);
    }

    private static void quickSort(int[] arr, int l, int r) {

        if (l >= r) {
            return; } // To improve efficiency and reduce the probability that the recursive tree causing quicksort is not uniform, // For an array, the probability that each random selection is the smallest and largest element in the current partition operation is reduced by 1/n! int randomNum = (int) (Math.random() * (r - l + 1) + l); swap(arr, l, randomNum); int v = arr[l]; Arr [l+1...lt] <v arr[lt+1.. I) =v arr[gt...r] > v arr[lt+1.. I) =v arr[gt...r] > v arr[gt...r lt = l; int gt = r + 1; int i = l + 1;while (i < gt) {
            if (arr[i] < v) {
                swap(arr, i, lt + 1);
                i++;
                lt++;
            } else if (arr[i] == v) {
                i++;
            } else{ swap(arr, i, gt - 1); gt--; // I ++ note that I does not need to be incremented by 1 because the value of I after the swap is still not equal to v, it may be less than or equal to v, so I will remain the same}} // After the loop ends, lt will be <v and the last element, I, will definitely overlap with gt V is not going to be where I is because I is the first element greater than v v // and v should be where lt is not where I is (arr [i-1] = arr[l]) swap(arr, L, lt); quickSort(arr,l,lt-1); quickSort(arr,gt,r); }Copy the code

Quicksort time complexity Space complexity

Since we most often use double-way fast sorting, we use this method for analysis: For convenient analysis, we assume that elements are not randomly selected, but the first element of the array is obtained. When the selected standard element and partition get position exchange, it is likely to disrupt the stability of the previous elements.

Let’s say the sequence is 5, 3, 3, 4, 3, 8, 9, 10, 11

Now swapping base elements 5 and 3(the fifth element, with subscripts starting at 1) would disrupt the stability of element 3. So quicksort is an unstable sorting algorithm that occurs when the base element is swapped with a[partition].

For quicksort, the time depends on the depth of its recursion. If the recursion depth is determined by the value of each key value, the middle value of the array is taken each time in the best case, then the optimal time complexity of the algorithm is O(nlogn). Of course, the worst case is the ordered array that we analyzed before, where we do n comparisons each time and the time is O(n ^ 2), but the average case is O(N logn), and again, if you want to go into more detail here we recommend a link quicksort best, worst, average complexity analysis

The space complexity of quicksort mainly depends on the temporary space when represented as selection, so it is linked to the time complexity, so the average space complexity is also O(nlogn).

conclusion

This paper summarizes the implementation of common sorting algorithms, through the study of these algorithms, is also helpful to solve the algorithm. We need to be familiar with these algorithms, but Android usually does not have to deal with too much data processing, so we need to deliberately review frequently. Most of the pictures in this paper come from the Internet, if there is any problem, you can send me a private message to delete. If you have any technical questions about what the article says, please feel free to contact me.

CSDN Github address

Analysis of the stability and time complexity of common sorting algorithms