2022-08-19 13:10:33
Ответ на
«Merge sort»
package main
import "fmt"
func Merge(left, right [] int) [] int{
merged := make([] int, 0, len(left) + len(right))
for len(left) > 0 || len(right) > 0{
if len(left) == 0 {
return append(merged,right...)
}else if len(right) == 0 {
return append(merged,left...)
}else if left[0] < right[0] {
merged = append(merged, left[0])
left = left[1:]
}else{
merged = append(merged, right [0])
right = right[1:]
}
}
return merged
}
func MergeSort(data [] int) [] int {
if len(data) <= 1 {
return data
}
done := make(chan bool)
mid := len(data)/2
var left [] int
go func(){
left = MergeSort(data[:mid])
done <- true
}()
right := MergeSort(data[mid:])
<-done
return Merge(left,right)
}
func main(){
data := [] int{9,4,3,6,1,2,10,5,7,8}
fmt.Printf("%v\n%v\n", data, MergeSort(data))
}
В начале при сортировке слиянием мы рекурсивно разделяем массив на right и left стороны и
на строках 30-34 вызываем MergeSort для обеих сторон.
Теперь нужно сделать так, чтобы Merge(left, right) выполнялась после получения возвращаемых значений от обоих рекурсивных вызовов, то есть и left и right должны обновляться до того, как Merge(left, right) сможет быть выполнена. Для этого на
строке 26 мы вводим канал типа bool и отправляем в него true сразу после выполнения left = MergeSort(data[:mid] (
строка 32).
Операция <-done блокирует код
на строке 35 до инструкции Merge(left,right), чтобы она не продолжилась, пока горутина не завершится. После завершения горутины и получения true в канале done код переходит к инструкции Merge(left, right)
на строке 36.
#задача
1.3K views10:10
G
