Mergesort не рассчитывает левый и правый размеры правильно для 1

Question

Я не уверен, почему левый размер и правый размер операций слияния, похоже, не работают для left = 0, mid = 0 и right = 1. Из-за этих calcs нарезка левого и правого массиване имеет никакого смысла.Алгоритм слияния предполагает, что один из этих массивов должен иметь значения, чтобы он даже находился в части кода слияния.Это приводит к ошибкам индекса: (

https://play.golang.org/p/Fmj4xNQTL8W

package main

import (
    "fmt"
)

func merge(arr []int, l, mid, r int) {
    leftSize := mid - l + 1
    rightSize := r - mid

    left := arr[l:mid]
    right := arr[mid+1 : r]

    fmt.Printf("l:%v, m:%v, r:%v\n", l, mid, r)
    fmt.Printf("left: size:%v arr:%v, right: size:%v arr:%v\n", leftSize, l, rightSize, r)

    /*
        i = left array pointer
        j = right array pointer
        k = original array pointer
    */
    i, j, k := 0, 0, l

    for i < leftSize && j < rightSize {
        if left[i] <= right[j] {
            arr[k] = left[i]
            i++
            k++
        } else {
            arr[k] = right[j]
            j++
            k++
        }
    }

    for i < leftSize {
        arr[k] = left[i]
        i++
        k++
    }
    for j < rightSize {
        arr[k] = right[j]
        j++
        k++
    }
}

func mergeSort(arr []int, left, right int) {
    if left >= right {
        return
    }

    // mid done this way to avoid overflows
    mid := left + (right-left)/2

    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)
    merge(arr, left, mid, right)
}

func main() {
    tc := []int{99, 212, 23, 3, 1, 10}
    mergeSort(tc, 0, len(tc)-1)
    fmt.Printf("%v", tc)
}

Answer 1

Я бы хотел предложить несколько вещей:

1. Диапазон массива.Дейкстра однажды спорил о том, как должен выглядеть диапазон массива (или в Go, диапазон срезов): что для нотации l[i:j] вы хотели бы, чтобы у нее были все эти свойства:

   • Он должен начинатьсяв i.
   • Это должно быть тривиально вычислить длину: len(l[i:j]) == j-i всегда верно
   • Это должно быть элегантно, чтобы выразить пустой диапазон, поэтому i<=j всегда верно

Следовательно, l [i: j] устанавливается как полуоткрытый диапазон: [i, j), нижняя граница включена и верхняя граница исключена.Это также способ среза Go (а также Python и многих других языков).

Дело в том, что лучше сохранить это соглашение в своем коде: при выполнении диапазона включайте нижнюю границуи исключить верхнюю границу.

Нарезка встроена в Go.Вы можете использовать это, и это дешево.Вам не нужно вычислять все эти l, r, mid таким многословным и подверженным ошибкам способом, вам просто нужно нарезать slice.

Дляпример:

func mergeSort(arr []int) {
    size := len(arr)

    if size <= 1 {
        return
    }
    mid := size / 2
    mergeSort(arr[:mid])
    mergeSort(arr[mid:])
    merge(arr, arr[:mid], arr[mid:])
}

Код намного понятнее и надежнее.

Срез не выполняет глубокое копирование, что означает, что left := arr[l:mid] создает только указатель на элементы arr.Вот почему я сказал, что нарезка дешево в го.

Однако без глубокого копирования при объединении фрагментов данные перезаписываются и, следовательно, повреждаются.Вам необходимо объединить новый фрагмент, а затем скопировать его обратно в оригинальный фрагмент.Вот почему считается, что наивный метод слияния имеет дополнительное использование памяти O(n).

func merge(arr, left, right []int) {
    res := make([]int, len(arr))
    leftSize, rightSize := len(left), len(right)

    var i,j,k int
    for i = range res {
        if j >= leftSize || k >= rightSize {
            break
        }

        if left[j] <= right[k] {
            res[i] = left[j]
            j++
        } else {
            res[i] = right[k]
            k++
        }
    }

    // Only one of these two copies run, so no need to increase i
    copy(res[i:], left[j:])
    copy(res[i:], right[k:])

    copy(arr, res)
}

Детская площадка: https://play.golang.org/p/LlJj-JycfYE

Answer 2

Не полный ответ, но некоторые предложения:

1. Вы можете избежать паники, изменив индексирование фрагментов:

до:

    left := arr[l : mid]
    right := arr[mid+1 : r]

после:

    left := arr[l : mid+1]
    right := arr[mid : r]

Вы можете распечатать содержимое левого и правого массива для отладки того, что происходит на каждом шаге.Печать размера не так полезна, как просмотр содержимого:

до:

fmt.Printf("left: size:%v arr:%v, right: size:%v arr:%v\n", leftSize, l, rightSize, r)

после:

fmt.Printf("left: size:%v arr:%v, right: size:%v arr:%v\n", left, l, right, r)