preface

Although the bubble sort of the last share is relatively simple and easy to understand, each bubble process needs to compare adjacent elements in turn, and then swap, so there is still a lot of room for optimization, as long as the number of comparisons can be reduced, the performance will naturally improve; Quicksort is a good choice

The body of the

1.1 Idea of quicksort algorithm

Quicksort is an improvement on the bubble sort algorithm shared last time. It mainly reduces the number of comparisons to improve the sort performance. It’s also a commutative sort.

Algorithm thought

  • Take any element in the list to be sorted as a reference value;
  • The remaining elements are compared with the base value in turn, the ones less than are put on the left, and the ones greater than are put on the right. Finally, the list to be sorted is divided into left and right parts through a sorting process, which is called a “partition”.
  • Then use the same method respectively in the left and right parts of the base value for sorting, recursion in turn, until the division of each part only one element or empty, the sorting end.

1.2 Implementation and analysis of quicksort algorithm

  • Algorithm implementation

    Division code implementation, each time take the first element of the corresponding part as a reference value, and then through sequential comparison, the corresponding data is subdivided into left and right parts, as follows:

    Partition sort using recursion until there is only one element or nothing:

  • Running effect

  • Step resolution (ascending) :

    Above steps:

    The first time all the data are grouped together, low is 0, high is 5, select the low element 2 as the reference value (i.e. the first element), and start the comparison:

    Step 1.1: Since the element with low position was selected as the reference value at the beginning (it can be considered that this position is empty), then the comparison was traversed from high position. The element with high position 3 is greater than 2, so there is no need to change positions.

    Step 1.2: At this point, low is 0, high is 4, element 9 of high is greater than 2, there is no need to change positions, high is reduced by 1, and the comparison continues.

    Step 1.3: At this point, low is 0, high is 3, and element 1 of high is less than 2. It is necessary to place element 1 of high to the left of the reference value, so element 1 is placed at the position pointed to by Low.

    Step 1.4: At this time, low is 0 and high is 3. Since the high bit has been swapped (it can be considered that the position is empty), we start to traverse the low bit for comparison this time. The low bit elements have just been swapped, so there is no need to swap positions. At this point, low is 1, and the element 5 at the corresponding position is greater than the reference value 2. Therefore, it is necessary to put element 5 to the right of the reference value, and then put element 5 to the position pointing to high.

    Step 1.5: At this time, low is 1 and high is 3. Since the low bit has been swapped (it can be considered that the position is empty), we return to the high bit for traversal comparison this time. The elements of the high bit have just been swapped, so there is no need to swap positions. At this time, high is 2, and the element 6 at the corresponding position is greater than the base value 2. Therefore, there is no need to change positions, and high is reduced by 1 to continue the comparison.

    Step 1.6: At this time, low is 1 and high is 1. At this time, it represents the completion of the first sorting, so the reference value is placed at this position. Finally, the original data is divided into left and right parts. The left part has only one element (1), so there is no need to divide it further. The right part has four elements (6,5,9, and 3).

    Step 2.1: Since the right part starts from index bit 2, low is 2, high is 5, and element 6 whose reference value is low is;

    Step 2.2: Since the element at low is selected as the base value (it can be considered that this position is empty), the comparison is traversed from high. High means that element 3 is less than base element 6, and it needs to be placed to the left of the base element, so element 3 is placed at the position pointed to by Low.

    Step 2.3: At this time, low is 2 and high is 5. Since the high bit has been swapped (it can be considered that the position is empty), we start to traverse the low bit for comparison this time. The low bit elements have just been swapped, so there is no need to swap positions. At this point, low is 3. The element 5 at the corresponding position is less than 6. There is no need to swap elements.

    Step 2.4: At this point, low is 4 and high is 5. The element 9 corresponding to low is greater than the base value 6, so it needs to be placed to the right of the base element, and then element 9 is placed at the position pointed to by high.

    Step 2.3: At this time, low is 4 and high is 5. Since the low bit has been swapped (it can be considered that the position is empty), we start to traverse the comparison to the high bit this time. The elements of the high bit have just been swapped, so there is no need to swap positions. High is reduced by 1 to continue the comparison. Now high is 4, and both Low and high are 4. Find the position of the reference value of this division, then put the reference element 6 at position 4. Here we divide the original right part 6,5,9, and 3 into left and right parts, and we have only one element 9 on the right side, so we don’t have to continue dividing; On the left, we have elements 3 and 5, and we keep sorting; (I will not repeat the demo here)

    Finally, the sorting result can be obtained by recursively dividing and sorting until there is only one element or empty in each partition part.

1.3 Analysis of quicksort algorithm

Time complexity

It can be seen from the above analytical steps that each sorting only needs to process the remaining unsorted elements, and the time complexity of each sorting will not exceed O(n). However, since the sorting is divided by recursion, the overall time complexity of quicksort is related to the number of recursive layers, that is, the total time complexity is O(n* number of recursive layers).

According to the above demonstration, the data to be sorted is actually divided into a binary tree structure, and the height of the binary tree represents the number of recursive layers (this content will be specially shared later), as shown below:

The minimum height of the binary tree of n elements is (log2n)+1, and the maximum height is N. If the data to be sorted has been ordered or reversed, if the first element of each part is selected as the reference value every time, the height of the binary tree will increase, that is, the recursive depth will increase. So the time complexity of quicksort is O(nlog2n) at best and O(n2) at worst.

Does that mean quicksort doesn’t work? Of course not, you can pick a random element as a reference value, so that the sorted data, whether ordered or reversed, will not cause too much recursion. So the average time complexity of the final quicksort is O(nlog2n).

Spatial complexity

Spatial complexity In each recursion, the variables used are fixed (pivot, Low,high), then the final factor affecting spatial complexity is still the number of recursive layers, so the complexity of quicksort space is O(number of recursive layers), O(log2n) at best, O(n) at worst.

The stability of

Because the data to be sorted is compared with the reference value, the final exchange position of elements is not fixed, so the original order of two equal elements cannot be guaranteed to remain unchanged, so quicksort is unstable. The diagram below:

If you take element 3 at low as the base value, you’ll end up swapping with element 2, and you won’t be able to keep the order of the original equal elements.

To sum up, quicksort is an unstable algorithm with time complexity O(nlog2n) and space complexity O(log2n).

conclusion

Quicksort effectively solves the defect of bubble sort, reduces the comparison times and improves the sorting performance. However, when the list to be sorted is ordered or in reverse order, the sorting performance does not improve if the first or last element is simply taken as the reference value. So the key to the implementation of the sorting algorithm is to choose a good reference value, such as random selection, can also define a rule selection, depending on the implementation of partners.

Thank you for your likes, favorites and comments. Continue next time **~~ **

A handsome guy who was made ugly by the program, pay attention to “Code variety circle “, learn with me ~~~