golang sort part of a slice using sort.Slice

陈建谟 0
Viewed 55

It's easy to sort a slice using sort.Slice in Golang, for example

func sortAll(nums []int) {
    sort.Slice(nums, func(i, j int) bool {
        if nums[i] < nums[j] {
            return true
        } else {
            return false
        }
    })
}

input : []int{2, 0, 1, 0, 1, 2, 2, 2} output:[0 0 1 1 2 2 2 2]

It works great.

However, if I want to sort a slice from some certain position, which means I just want to sort part of the slice. I used this piece of code:

func sortPartly(nums []int, p int) {
    sort.Slice(nums[p:], func(i, j int) bool {
        if nums[i] < nums[j] {
            return true
        } else {
            return false
        }
    })
}

With the same input, I use sortPartly(nums, 1) to set the position to start sorting to be 1. And I got output [2 0 1 1 2 2 2 0] which isn't in order from nums[1],the output should be [2 0 0 1 1 2 2 2]

After some debugging, I happend to write this piece of code below, it worked just as I wanted. But I don't understand why this code works

func sortPartly(nums []int, p int) {
    sort.Slice(nums[p:], func(i, j int) bool {
        if nums[i+p] < nums[j+p] {
            return true
        } else {
            return false
        }
    })
}

I have a toy code to save your time, can anyone help me explain why this code works. Go Playground

slice go sorting
1 Answers

Here's the code that works from the question:

func sortPartly(nums []int, p int) {
    sort.Slice(nums[p:], func(i, j int) bool {
        if nums[i+p] < nums[j+p] {
            return true
        } else {
            return false
        }
    })
}

This function sorts the slice nums[p:]. This slice shares a backing array with nums, but uses different indices for the elements in that backing array. The element at index 0 is at index p in nums. The element at index 1 is at index p + 1 in nums and so on. Because sort.Slice uses indices into the slice nums[p:] and the anonymous function refers to slice nums, the anonymous function must adjust the indices by adding p.

Eliminate the index adjustment by declaring the slice to sort. Refer to that slice in the anonymous function.

func sortPartly(nums []int, p int) {
    t := nums[p:]
    sort.Slice(t, func(i, j int) bool {
        if t[i] < t[j] {
            return true
        } else {
            return false
        }
    })
}

Note that t shares a backing array with nums. Sorting t sorts elements in nums.

Bonus suggestion: Simplify the construct if boolValue { return true } else { return false } to return boolValue.

func sortPartly(nums []int, p int) {
    t := nums[p:]
    sort.Slice(t, func(i, j int) bool {
        return t[i] < t[j]
    })
}
melinda0
Related