Most efficient method for maintaining a sorted slice

Written by
reddit
Link to Post

https://www.reddit.com/r/golang/comments/b0gro0/most_efficient_method_for_maintaining_a_sorted/ by 

I’m looking for a method that is efficient for maintaining a sorted slice of structs by a specific value within the struct.

This may be a more general CS question and I’m going off of memory here from an older CS Algo book — but would it be more efficient to append a new element to a sorted list and then do an insertion or bubble sort or would it be better to use a heap approach?

Super simple example using just a slice of ints:

s := []int{1,2,3,4,5,7,8,9} err := InsertSorted(s,6) // s is now [1 2 3 4 5 6 7 8 9] from appending 6 to the end of s and then doing an insertion or bubble sort 

Ideas:

  1. Simply append the new element to the slice and do an insertion / bubble sort.
  2. Have the function find the index of where the element should be inserted and use copy / append to create a new slice from the existing slice where the element is in the proper location and return the new slice. (This could be expensive for large slices in terms of memory)
  3. Use a heap approach.

I’m not sure what approach would be best for slices with a large size (in the millions). There are probably some optimizations one could do here — but I don’t know what they would be in Go. FYI — I just started using Go a few days ago.

Thanks!

Edit: Actually, insertion / bubble has a best time of O(n) which may not be ideal — adding one element to an already sorted list should allow for an O(log n) operation — but memory optimization would probably not be O(1) here. It seems one could do a O(log n) binary search to find the index the new element would be placed and then break the slices into two and append them with the element at the proper index — so this would be efficient but require more memory. Any ideas?

submitted by /u/Stuck_In_the_Matrix
[link] [comments]

Article Tags:
· ·
Article Categories:
reddit

Leave a Reply