1. Problem
Divide and conquer algorithm means to split a complex problem into several similar subproblems until each subproblem can be solved simply and directly.
Divide and conquer algorithms are the basis of many efficient algorithms, such as subsumption sorting, quick sorting, dichotomous search methods, etc., all use the idea of Divide and conquer algorithms
The recursive algorithm is one of the most important ideas of Divide and conquer.
2. find the maximum value
2.1. General algorithm
Given a random array, select the maximum and minimum values from it.
The easiest way to find the maximum and minimum values is to iterate through the loop.
The implementation in GO language is as follows.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
package main
import (
"fmt"
"math/rand"
)
func main() {
var length int = 100
var random []int
for i := 0; i < length; i++ {
random = append(random, rand.Intn(length))
}
fmt.Println("Array length: ", length)
var minNumber int = random[0]
var maxNumber int = random[0]
for i := 1; i < len(random); i++ {
if random[i] > maxNumber {
maxNumber = random[i]
}
if random[i] < minNumber {
minNumber = random[i]
}
}
fmt.Printf("Max number:%v\nMin number:%v\n", maxNumber, minNumber)
}
|
1
2
3
|
Array length: 100
Max number:99
Min number:0
|
The ordinary algorithm is the most conventional solution.
2.2. Divide and conquer algorithm
Given a random array, the maximum and minimum 2 values are selected from it.
We use Divide and conquer algorithm to handle this.
The implementation in GO language is as follows.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
package main
import (
"fmt"
"math/rand"
)
func GetMaxByArray(array []int, left int, right int) int {
// 空列表表示出错
if len(array) == 0 {
return -1
}
// 下标相撞则直接判断大小
if right-left <= 0 {
if array[left] >= array[right] {
return array[left]
}
return array[right]
}
var middle = int((right-left)/2) + left
var maxLeft = GetMaxByArray(array, left, middle)
var maxRight = GetMaxByArray(array, middle+1, right)
if maxLeft >= maxRight {
return maxLeft
}
return maxRight
}
func GetMinByArray(array []int, left int, right int) int {
// 空列表表示出错
if len(array) == 0 {
return -1
}
// 下标相撞则直接判断大小
if right-left <= 0 {
if array[left] >= array[right] {
return array[right]
}
return array[left]
}
var middle = int((right-left)/2) + left
var maxLeft = GetMinByArray(array, left, middle)
var maxRight = GetMinByArray(array, middle+1, right)
if maxLeft >= maxRight {
return maxRight
}
return maxLeft
}
func main() {
var length int = 100
var random []int
for i := 0; i < length; i++ {
random = append(random, rand.Intn(length))
}
fmt.Println("Array length:", length)
var maxNumber = GetMaxByArray(random, 0, len(random)-1)
var minNumber = GetMinByArray(random, 0, len(random)-1)
fmt.Printf("Max number:%v\nMin number:%v\n", maxNumber, minNumber)
}
|
1
2
3
|
Array length: 100
Max number:99
Min number:0
|
The Divide and conquer algorithm splits the array of length 100 into 2 arrays of 50, and then splits the 2 arrays of 50 into 2 arrays of 25.
This recursion is repeated until the array length is 2, then the size can be compared directly, which does not reduce the size of the problem.
Here we can see the 3 steps of Divide and conquer algorithm implementation.
- disassembly: the original problem is disassembled into a number of smaller subproblems of the same form.
- solve: sub-problems are solved directly if the size of the problem is consistent with the direct solution, otherwise recursive disassembly.
- merge: merge the subproblems into a solution of the problem.
The above example is simple but reflects the idea of Divide and conquer algorithm.
The following is an example of subsorting algorithm and fast sorting algorithm.
See how the idea of Divide and conquer algorithm is applied in the sorting algorithm.
3. Array sorting
Given 10 random numbers as an array arr, sort the array arr.
3.1. merge sort
The implementation of the merge sort algorithm is as follows
- divide: recursive array is divided equally into 2 parts.
- Merge: Maintain the order of elements and merge all subsequences.
The time complexity of the merge algorithm is O（nlogn）, and the merge sort is a stable sorting algorithm.
sorting algorithm stability: means that after sorting still maintain the original array index size relationship, such as [2,3,1,4,5,3] after sorting [1,2,3,3,4,5], where the two numbers “3” array index are 1, 5, and then sorted after the index size relationship still holds.
The recursive version of the GO language is implemented as follows.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
package main
import (
"crypto/rand"
"fmt"
"math/big"
"time"
)
func Merge(arr []int) []int {
var arr_len = len(arr)
// 将数组分为2部分，对左边部分再进行分组，直到数组长度不大于2
var left_arr = arr[:arr_len/2]
var left_arr_len = len(left_arr)
if left_arr_len >= 2 {
left_arr = Merge(left_arr)
}
// 将数组分为2部分，对右边部分再进行分组，直到数组长度不大于2
var right_arr = arr[arr_len/2:]
var right_arr_len = len(right_arr)
if right_arr_len >= 2 {
right_arr = Merge(right_arr)
}
// 对数组进行排序
var left_index int = 0
var right_index int = 0
var sort_arr = make([]int, arr_len)
for i := 0; i < arr_len; i++ {
if right_index == right_arr_len {
sort_arr[i] = left_arr[left_index]
left_index++
continue
}
if left_index == left_arr_len {
sort_arr[i] = right_arr[right_index]
right_index++
continue
}
if left_arr[left_index] <= right_arr[right_index] {
sort_arr[i] = left_arr[left_index]
left_index++
continue
}
if left_arr[left_index] > right_arr[right_index] {
sort_arr[i] = right_arr[right_index]
right_index++
continue
}
}
return sort_arr
}
func main() {
var length int = 10
var randoms []int
for i := 0; i < length; i++ {
// 产生真随机数（性能较差）
n, _ := rand.Int(rand.Reader, big.NewInt(int64(length)))
randoms = append(randoms, int(n.Int64()))
}
fmt.Println("Source array: ", randoms)
var start = time.Now()
var sortRandoms = Merge(randoms)
var elapsed = time.Since(start)
fmt.Println("Sort array: ", sortRandoms)
fmt.Println("Total time: ", elapsed)
}
|
1
2
3
|
Source array: [5 5 4 3 7 1 0 8 7 8]
Sort array: [0 1 3 4 5 5 7 7 8 8]
Total time: 7.291µs
|
The subsumption algorithm can also be implemented iteratively and is not described here
3.2. Fast sorting algorithm
Fast sorting principle
- pick: select a base value
- swap: the elements greater than the base value are swapped to the right of the base value and elements less than the base value are swapped to the left
- Recursive: Consider each left/right of the base value as an array and continue recursive quick sort
Quick sort algorithm is an unstable sorting algorithm, based on bubble sort algorithm improvement
Time complexity
- Average time complexity: O(nlogn)
- Worst case: O(n2)
The GO language implementation is as follows.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
package main
import (
"crypto/rand"
"fmt"
"math/big"
"time"
)
func QuickSort(array []int, left int, right int) {
if len(array) <= 1 || left >= right {
return
}
// 对数组进行基准（pivot）排序
var mid = Partition(array, left, right)
QuickSort(array, left, mid)
QuickSort(array, mid+1, right)
}
func Partition(array []int, left int, right int) int {
// 取pivot的值为数组最后一个元素
var pivotIndex int = right
// 从左往右遍历数组寻找大于pivot值的元素A，从右往左寻找小于pivot值的元素B，交换元素A与B的位置，直到rightIndex与leftIndex相等
// 遍历结束后，rightIndex（leftIndex）下标数组左边元素均小于pivot值，右边均大于pivot值
var rightIndex int = right - 1
for leftIndex := left; leftIndex < rightIndex; leftIndex++ {
if array[leftIndex] > array[pivotIndex] {
for ; rightIndex > leftIndex; rightIndex-- {
if array[rightIndex] < array[pivotIndex] {
var temp int = array[rightIndex]
array[rightIndex] = array[leftIndex]
array[leftIndex] = temp
break
}
}
}
}
// 因pivot值为数组最后一个元素，若pivot值小于数组下标rightIndex（leftIndex），则交换彼此元素位置
if array[rightIndex] > array[pivotIndex] {
var temp int = array[rightIndex]
array[rightIndex] = array[pivotIndex]
array[pivotIndex] = temp
}
return rightIndex
}
func main() {
var length int = 10
var randoms []int
for i := 0; i < length; i++ {
// 产生真随机数（性能较差）
n, _ := rand.Int(rand.Reader, big.NewInt(int64(length)))
randoms = append(randoms, int(n.Int64()))
}
fmt.Println("Source array: ", randoms)
var start = time.Now()
var elapsed = time.Since(start)
QuickSort(randoms, 0, len(randoms)-1)
fmt.Println("Sort array: ", randoms)
fmt.Println("Total time: ", elapsed)
}
|
1
2
3
|
Source array: [8 4 6 5 3 5 8 4 9 1]
Sort array: [1 3 4 4 5 5 6 8 8 9]
Total time: 220ns
|