CODEWITHSUNDEEP
arrayssortinggo
unsafe_where_true
unsafe_where_true

Reputation: 6310

Sort while appending to slice?

I have a []byte which I need to sort, in ascending order.

I get an object with the items and then iterate the array in order to create the object returned:

// unfortunately, for some obscure reason I can't change the data types of the caller and the object from the function call are different, although both are []byte underneath (...)

type ID []byte
// in another package:
type ByteInterface []byte


func (c *Store) GetAll() ByteInterface {
  returnObj := make([]ByteInterface,0)
  obj, err := GetData()
  // err handling
  for _, b := range obj.IDs {
     returnObj = append(returnObj, ByteInterface(b))
  }
  return returnObj
}

So I'm asking myself if it is possible to do the append so that returnObj is sorted right away, or if I need to sort obj.ByteData upfront (or sort returnOjb afterwards).

Upvotes: 2

Views: 1847

Answers (1)

kostix
kostix

Reputation: 55513

On each iteration, do the following:

  1. Grow the target slice (possibly reallocating it):

    numElems := len(returnObj)
returnObj = append(returnObj, make([]byte, len(obj))...)

  2. Use the standard approach for insertion to keep the destination sorted by finding a place to put each byte from the source slice, one by one:

    for _, b := range obj {
  i := sort.Search(numElems, func (i int) bool {
    return returnObj[i] >= b
  }
  if i < numElems {
    copy(returnObj[i+1:], returnObj[i:])
  }
  returnObj[i] = b
  numElems++
}

    (The call to copy should be optimized by copying less but this is left as an exercise for the reader.)

Upvotes: 5

Related Questions