preface
This is the seventh day of my participation in the August More text Challenge. For details, see: August More Text Challenge
The top ten sorts are: bubble sort, selection sort, insertion sort, Hill sort, merge sort, quicksort (quicksort), bucket sort, count sort, radix sort, and heap sort.
This article focuses on the principles and implementation of merge sort and quicksort, and a simple comparison between the two.
If you want to understand each sort of time complexity comparison, as well as some sort of basic knowledge, such as stable sort and non-stable sort, in situ sort and non situ sort, you can see the hand tore sorting algorithm ten (preface), I believe can help you!
Note: This code is implemented by Golang.
Quick sort
Quicksort, also known as partition-exchange sort, got its name from the saying “quicksort is usually faster than other algorithms”.
Quicksort is essentially a dial-and-conquer algorithm. The idea is to select a reference value (also called the principal element) from a bunch of numbers. By traversing the numbers, put the numbers less than the reference value on the left and the numbers greater than the reference value on the right; Do the same with the left and right arrays (recursion) until the subarrays can no longer be partitioned, and finally merge the subarrays (since they are already sorted) to create a sorted array.
In most articles, it is mentioned that quicksort is an algorithm that sorts in place, that is, does not apply for extra space, but more accurately, whether quicksort is in place depends on how you implement it, it can be either in place or not in place, as described below.
Non-locked-in version
The non-in place version is shown first because it is easier to understand.
As I said, quicksort is a divide and conquer algorithm, so it’s often done recursively, and when you do recursion, the first thing you need to do is to know the end of the recursion condition, which in this case is when the length of the subarray is less than or equal to 1, because it’s only one element, and you can’t sort anymore.
The next step is to split the array using the reference value, which is the default value for the first element. The choice of the reference value also affects the quicksort time (we’ll see later), and the last step is to combine the two subarrays with the reference value.
// Quicksort: non-location-based version
func quickSort1(arr []int) []int {
n := len(arr)
// The end condition of recursion
if n <= 1 {
return arr
}
left, right := []int[] {},int{}
// Select a reference value. In this case, the first element is the reference value
base := arr[0]
arr = arr[1:]
// Split the array
for _, num := range arr {
if num < base {
left = append(left, num)
} else {
right = append(right, num)
}
}
// Merge the left and right arrays and their reference values
result := append(quickSort1(left), base)
result = append(result, quickSort1(right)...)
return result
}
Copy the codeThe in-place version
For the version of in-place sorting, there are actually two kinds. One is to select the first element as the base value by default, and the other is to select the last element as the base value by default. The principle of both is the same, but the partition algorithm is written differently.
Here to the first element as the reference value of the writing method, explain the quick sort in place of the train of thought:
First, we need three Pointers to sort in place: a reference, an I pointer, and a k pointer. The left side of the I pointer is smaller than the reference, and the right side of the I pointer is larger than the reference (which is still to be compared). The k pointer does the traversal.
In the first round of traversal, the pointer k goes to 13, which is larger than the base value, and continues to go to 5, which is smaller than the base value. At this time, the pointer I needs to move one step and exchange values with the pointer K.
In the second round of traversal, the k pointer continues to go to the position 3 and finds that it is lower than the base value again, the I pointer moves one more step, and the two switch.
The third iteration is the same thing.
After the third round of traversal, the first round of sorting has been completed. By default, we select the first element as the reference value, so we need to swap the I pointer with the reference value, so that the value less than the reference value is on the left, and the value greater than the reference value is on the right!!
Using the first element as a reference value
// Quicksort: sort in place version
// The first element is selected by default
func quickSort2(arr []int, startIdx, endIdx int) {
// Recursive cutoff condition
if startIdx >= endIdx {
return
}
// P is the reference value
p := partition(arr, startIdx, endIdx)
// Sort the subarray, because p is the reference value, so do not go to the next round of sorting
quickSort2(arr, startIdx, p- 1)
quickSort2(arr, p+1, endIdx)
}
// Partition the array and return the reference value for the next partition
func partition(arr []int, startIdx, endIdx int) int {
// Set the reference value
base := arr[startIdx]
i := startIdx
// Move all elements less than the base value to the left
for k := startIdx + 1; k <= endIdx; k++ {
if arr[k] < base {
i++
arr[k], arr[i] = arr[i], arr[k]
}
}
// This step puts the reference value after the element smaller than it
arr[i], arr[startIdx] = arr[startIdx], arr[i]
return i
}
func quickSort2Test(a) {
nums := []int{6.10.13.5.8.3.2.11}
quickSort2(nums, 0.len(nums)- 1)
fmt.Println(nums)
}
Copy the codeThe writing of a value based on the last element
// Quicksort: sort in place version
// The last element is selected by default
func partition2(arr []int, startIdx, endIdx int) int {
/ / value
base := arr[endIdx]
i := startIdx - 1
// This step moves all elements less than the base value to the front
for k := startIdx; k < endIdx; k++ {
if arr[k] < base {
i++
arr[k], arr[i] = arr[i], arr[k]
}
}
// This step puts the reference value after the element smaller than it
arr[i+1], arr[endIdx] = arr[endIdx], arr[i+1]
return i + 1
}
func quickSort3(arr []int, startIdx, endIdx int) {
// Recursive cutoff condition
if startIdx >= endIdx {
return
}
p := partition2(arr, startIdx, endIdx)
quickSort3(arr, startIdx, p- 1)
quickSort3(arr, p+1, endIdx)
}
func quickSort3Test(a) {
nums := []int{6.10.13.5.8.3.2.11}
quickSort3(nums, 0.len(nums)- 1)
fmt.Println(nums)
}
Copy the codeOn the time complexity of quicksort: The complexity of quicksort depends on the base value selected. When the array itself is in order (positive or reverse) and the first element is selected as the base value each time, the number of partitions is O (n).
If the base value selected every time happens to be the intermediate value, then the number of partitions becomes O(logn), and the complexity of the elements partition according to the base value is O(n) each time, so the average complexity of quicksort is O(nlogn), the optimal time complexity is O(nlogn), and the worst time complexity is O($n^2$).
For example, arR = [1, 2, 2, 3, 4, 5, 6] : In the partition stage of quicksort, if arR [2] is selected as the base value and the value greater than or equal to 2 is placed in the large number array, that is, arR [1] will go to the right of the base value, then the two 2’s in the array are not consistent with the original order, and the sort is unstable.
Similarly, if arr[1] is selected as the base value, and the value less than or equal to 2 is placed in the decimal array, that is, arR [2] will go to the left of the base value, then the two 2’s in the array are not in the same order as the original, and the sorting is unstable.
Merge sort
If you’ve seen quicksort before, and you look at merge sort, you’ll see that they’re actually very similar, because quicksort is recursively partitioning arrays, and merge sort is recursively merging arrays, and that’s why I’m putting them together.
Steal others’ picture here, you can see the early stage of the merge sort to put large array divided into small array, and when the array divided enough hours (1) in length, then compare about the size of the two sub array, and synthesis of a new array, layers of recursion, eventually merged array is a sorted array.
Note: Picture source here, tort delete
/ / merge
func merge(left []int, right []int) []int {
leftIdx, rightIdx := 0.0
result := []int{}
for leftIdx < len(left) && rightIdx < len(right) {
if left[leftIdx] <= right[rightIdx] {
result = append(result, left[leftIdx])
leftIdx += 1
} else {
result = append(result, right[rightIdx])
rightIdx += 1}}// There are two cases of the for loop:
// 1. The left array has the same length as the right array
// 2. If the left array and the right array have different lengths, either of them must have extra elements, and these elements need to be copied to the end of the queue
result = append(result, left[leftIdx:]...)
result = append(result, right[rightIdx:]...)
return result
}
func mergeSort(arr []int) []int {
n := len(arr)
if n <= 1 {
return arr
}
split := n / 2
// Partition the left subarray
left := mergeSort(arr[:split])
right := mergeSort(arr[split:])
return merge(left, right)
}
Copy the codeWhether merge sort is stable: As you can see from the partition process above, merge sort only compares pairwise, and there is no quicksort partition by reference, so it is stable.
On whether merge sort is in place: As you can see from the code implementation above, merge sort requires an intermediate array to store the sorted values, so it is not in place.
On the time complexity of merge sort: merge sort partition part time is O(logn), merge part time is O(n), so the total time is O(nlogn).
Merge sort VS quicksort
1. Reference value: Merge sort does not require a reference value, while quicksort requires one
2. Stability: Merge sort is stable, but not in place; Quicksort is not a stable sort, but it can be implemented in place.
3. Processing: Quicksort divides arrays recursively, merge sort merges arrays recursively
Note: A graph of Geek Time is cited here for better understanding
Write in the last
If there are any mistakes in this article, please point them out in the comment section, and thank you very much. In addition, if this article is useful to you, please also ask guests to point a little love 💖!