Как исправить одновременную сортировку слиянием в го - PullRequest
Новая
       28

Как исправить одновременную сортировку слиянием в го

1 голос
/ 25 июня 2019

Я пытаюсь научиться идти вперед и сталкиваюсь с проблемами при одновременной реализации сортировки слиянием.Неправильная сортировка массива

Я пытался найти какие-либо условия гонки, а также пытался печатать на разных этапах.Но не могу понять проблему.Любой инструмент для анализа и выявления таких проблем. 

package main

import (
    "fmt"
    "time"
)

func merge(a []int, ch chan int) {
    //     defer close(ch)
    if len(a) == 0 {
        close(ch)
        return
    }

    if len(a) == 1 {
        ch <- a[0]
        close(ch)
        return
    }

    mid := len(a) / 2

    ch1 := make(chan int)
    go merge(a[:mid], ch1)

    ch2 := make(chan int)
    go merge(a[mid:], ch2)

    v1, ok1 := <-ch1
    v2, ok2 := <-ch2
    var t []int
    for ok1 == true && ok2 == true {
        if v1 < v2 {
            ch <- v1
            t = append(t, v1)
            v1, ok1 = <-ch1
        } else {
            ch <- v2
            t = append(t, v2)
            v2, ok2 = <-ch2
        }
    }
    close(ch)
}

func Merge(a []int) (sortedA []int) {
    ch := make(chan int)
    go merge(a, ch)

    for v := range ch {
        sortedA = append(sortedA, v)
    }
    return
}

func main() {
    arr := []int{3, 34, 23, 65, 34, 7, -1, 0, -23}
    start := time.Now()
    b := Merge(arr)
    fmt.Printf("Time taken to sort: %v, sorted: %v", time.Since(start), b)
}

Я ожидал, что результат будет [-23 -1 0 3 7 23 34 34 65], но фактический результат составляет всего -23

1 Ответ

1 голос
/ 25 июня 2019

Ваша фаза слияния нарушена: вы должны отправить ch все значения от ch1 и ch2, но ваш код останавливается один раз любой из ch1 или ch2 сливается. Как только вы слили, например, ch2 Вы должны отправить все от ch1 до c.

Что-то не так (не забудьте очистить условия!) 

for ok1 || ok2 {
    if (ok1 && ok2 && v1 < v2) || (ok1 && !ok2) {
        ch <- v1
        v1, ok1 = <-ch1
    } else if (ok1 && ok2 && v1 >= v2) || (!ok1 && ok2) {
        ch <- v2
        v2, ok2 = <-ch2
    }
}
...