CODEWITHSUNDEEP
sortinginsertjulia
Colin T Bowers
Colin T Bowers

Reputation: 18570

Insert item into a sorted list with Julia (with and without duplicates)

Main Question: What is the fastest way to insert an item into a list that is already sorted using Julia?

Currently, I do this:

v = [1, 2, 3, 5] #example list
x = 4 #value to insert
index = searchsortedfirst(v, x) #find index at which to insert x
insert!(v, index, x) #insert x at index

Bonus Question: What if I want to simultaneously ensure no duplicates?

Upvotes: 7

Views: 3116

Answers (2)

Bruno Castro
Bruno Castro

Reputation: 29

For sorted arrays of structs a modified version of StefanKarpinski solution would look like the example below:

struct TimeEvent
    date::Dates.DateTime
    type::String
end
    
v = [
    TimeEvent(DateTime("2019-03-01"),"data_release") 
    TimeEvent(DateTime("2019-02-01"),"data_release") 
    TimeEvent(DateTime("2019-05-01"),"data_release") 
 ]

new_event=TimeEvent(DateTime("2019-04-01"),"data_release") 

# Sort Events
sort!(v, by = v -> v.date, rev=true) 

# Define Function
sortedStructInsert!(v::Vector, x) = (splice!(v, 
    searchsorted(v,x,by= v->v.date, rev=true), [x]); v)

# Call function
sortedStructInsert!(v, new_event)

4-element Vector{TimeEvent}:
 TimeEvent(DateTime("2019-05-01T00:00:00"), "data_release")
 TimeEvent(DateTime("2019-04-01T00:00:00"), "data_release")
 TimeEvent(DateTime("2019-03-01T00:00:00"), "data_release")
 TimeEvent(DateTime("2019-02-01T00:00:00"), "data_release")

The example below allows you to specify which field of the struct is the one that sorts, for a more generic implementation.

sortedStructInsert!(v::Vector, x,symbol) = (splice!(v,
    searchsorted(v,x,by= v->getproperty(v,symbol), rev=true), [x]); v)
sortedStructInsert!(v, new_event, :date)

Upvotes: 0

StefanKarpinski
StefanKarpinski

Reputation: 33290

You can use searchsorted to get the range of indices where the value occurs instead of just the first one and then use splice! to replace the values in that range with a new set of values:

insert_and_dedup!(v::Vector, x) = (splice!(v, searchsorted(v,x), [x]); v)

That's a nice little one-liner that does what you want.

julia> v = [1, 2, 3, 3, 5];

julia> insert_and_dedup!(v, 4)
6-element Array{Int64,1}:
 1
 2
 3
 3
 4
 5

julia> insert_and_dedup!(v, 3)
5-element Array{Int64,1}:
 1
 2
 3
 4
 5

This made me think that splice! should handle the case where the replacement is a single value rather than an array, so I may add that feature.

Upvotes: 10

Related Questions