Quick Sort
Like merge sort, quicksort uses a dive-and-conquer strategy, but does not require additional storage. However, the efficiency of the algorithm will be reduced.
- The quicksort algorithm first picks a reference value. For simplicity, we select the first element in the slice array (hereinafter referred to as the list).
- The purpose of the reference value is to help shard the list.
- In the final ordered list, the position of the benchmark value is called the split point, and the algorithm splits the list into two parts at the split point, and then applies quicksort to the two parts.
Quicksort process
Suppose that the list [5, 3, 10, 1] needs to be sorted by quicksort algorithm in ascending order, and the process is as follows:
- Select a reference value: Element 5 will be the first reference value.
The partition operation starts by finding two coordinates — leftMark and RightMark — at the beginning and end of the remaining elements of the list, respectively, as shown in the figure below. The purpose of partitioning is to put the elements to be sorted on the right side based on their relative size to the reference value, while gradually approaching the split point. The figure below shows the process of finding the correct location for the base value element 5.
First, increase leftMark until you encounter an element greater than the base value. It then reduces the rightMark until it encounters an element less than the base value. In this way, we find two elements that are out of order from the final split point. In this case, the two elements are 10 and 1. Swap the positions of the two elements and repeat the process.
When rightMark is less than leftmark, the procedure terminates. In this case, the rightMark’s position is the split point. The reference value is in the correct position by interchanging it with the element currently at the split point, as shown in the figure above. All elements to the left of the split point are less than the reference value, and all elements to the right are greater than the reference value. Therefore, you can split the list in half at the split point and recursively call the quicksort function for the left and right parts.
Golang to achieve quick sort algorithm code
1. package main
2.
3. import "fmt"
4.
5. func quickSort(numList []int) {
6. quickSortHelper(numList, 0.len(numList)- 1)
7. }
8.
9. func quickSortHelper(numList []int, first, last int) {
10. if first < last {
11. // Calculate the cut point
12. splitPoint := partition(numList, first, last)
13. // Quicksort the data to the left of the cut point
14. // Quick sort for data smaller than the cut point
15. quickSortHelper(numList, first, splitPoint- 1)
16. // Quicksort the data to the right of the cut point
17. // Quick sort for data larger than the cut point
18. quickSortHelper(numList, splitPoint+1, last)
19. }
20. }
21.
22. func partition(numList []int, first, last int) int {
23. // Select the first number as the reference point
24. // Put the smaller data in the list to the left of the reference point
25. // Put the data larger than the reference point in the list to the right of the reference point
26. // And return to the cut point so that the cut can be made again
27. pivotValue := numList[first]
28. leftMark := first + 1
29. rightMark := last
30. done := false
31. // Find the cut point
32. for! (done) {33. // When the left buoy is moving from left to right
34. // And the left and right buoys do not cross
35. // If the left buoy value is less than the reference value, it will continue to move to the right
36. // If the left buoy is larger than the reference value, stop moving to the right
37. // means that the next value should be to the right of the reference value
38. for leftMark <= rightMark &&
39. numList[leftMark] <= pivotValue {
40. leftMark += 1
41. }
42.
43. // When the right buoy moves from right to left
44. // And the left and right buoys do not cross
45. // If the value of the right buoy is greater than the reference value, it will continue to move to the left
46. // If the right buoy value is less than the reference value, stop moving to the left
47. // means that this value should be to the left of the reference value
48. for rightMark >= leftMark &&
49. numList[rightMark] >= pivotValue {
50. rightMark -= 1
51. }
52.
53. // If the left and right buoys cross, the cut point is found
54. // Stop looking for cuts
55. if rightMark < leftMark {
56. done = true
57. } else {
58. // The left and right buoys are not crossed, but the left and right buoys are stopped
59. // That is, the values of the left and right buoys should be on the other side of the reference values
60. // Then you need to exchange the left and right buoy values
61. temp := numList[leftMark]
62. numList[leftMark] = numList[rightMark]
63. numList[rightMark] = temp
64. }
65. }
66.
67. // Move the data from the cut point to the reference value
68. numList[first] = numList[rightMark]
69. // Move the reference value to the correct position
70. numList[rightMark] = pivotValue
71. // Return the split point
72. return rightMark
73. }
74.
75.
76. func main(a) {
77. numList := []int{10.1.5.3.99}
78. quickSort(numList)
79. fmt.Println(numList)
80. }
Copy the codeIn the above code, the quickSort function calls the recursive function quickSortHelper.
QuickSortHelper first determines if it is in the base case.
- If the length of a list is less than or equal to 1, it is already an ordered list.
- If the length is greater than 1, partition and sort recursively.
Time complexity
- For a list of length n, if the partitioning operation always occurs in the middle of the list, logn times will be split.
- To find the split point, each of the N elements is compared to the reference value. So, the time complexity is order nlogn.
In addition, quicksort does not require the same amount of storage as merge sort.