CODEWITHSUNDEEP
pythonalgorithmlistsortinginsert
user2957178
user2957178

Reputation: 113

Inserting values into a sorted array

What would be the quickest way to insert values into the correct position in a sorted numpy array?

For example, I would like to insert every value of binto a:

a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70]

b = [5,7,9,45]

I've tried looping through a for each value of b and inserting it that way. I've also tried the bisect_left method: 

for i in b:
a.insert(bisect_left(a,i),i)

Both methods are too slow as I have hundreds of thousands of data elements to go through.

Any ideas?

Upvotes: 8

Views: 10892

Answers (5)

farzin vatani
farzin vatani

Reputation: 98

For a more pythonic approach, You can use bisect.insort(your_list, your_value) to insert a value into the correct position of a sorted list. Like this:

import bisect

a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70]
b = [5,7,9,45]

for value in b:
    bisect.insort(a, value)

# Now a == [1, 1, 2, 4, 5, 7, 7, 7, 9, 11, 13, 13, 13, 15, 20, 25, 26, 27, 30, 45, 45, 70]

Upvotes: 2

Ill-Conditioned Matrix
Ill-Conditioned Matrix

Reputation: 441

You could use searchsorted and insert:

a = numpy.array([1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70])
b = numpy.array([5,7,9,45])
ii = numpy.searchsorted(a, b)
a = numpy.insert(a, ii, b)

Upvotes: 13

Samy Arous
Samy Arous

Reputation: 6814

let's note n = len(a) and m = len(b),

  1. you can use a binary search to find each element's position and insert it, that would done in m*n*log(n) time
  2. you can merge both arrays, that would have an n+m complexity
  3. you can use a specialized structure, a balanced binary tree, you can find a lot of implementation of these in python, the time complexity will be mlog(n)

Now given possible values of n and m, you can determine which solution is best, but don't expect to do better than that

Upvotes: 4

Анатолий
Анатолий

Reputation: 2857

You solution slow becaue you have a lot of inserts. Each insrt is O(N) complexity.

My solution: a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70] b = [5,7,9,45]

insert b.Length items into end of a. a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70,x,x,x,x] b = [5,7,9,45]

Take 3 pointers:

  1. Pointer into a to last actual element(in example pointer to 70)
  2. Pointer into b to last element(in example pointer to 45)
  3. POinter to last of a

Here my solution in C#:

    int p1 = a.Length - 1;
    int p2 = b.Length - 1;
    int p3 = a.Length + b.Length - 1;

    //Insert b.Length items to end of a.

    while (p3 >= 0 && p2 >= 0)
    {
        if (p1 < 0 || b[p2] >= a[p1])
        {
            a[p3--] = b[p2--];
        }
        else
        {
            a[p3--] = a[p1--];
        }
    }

Upvotes: -3

thefourtheye
thefourtheye

Reputation: 239473

Just use builtin sort method. It implements timsort. If the list is almost sorted, it will be very fast.

a.extend(b)
a.sort()

Upvotes: 4

Related Questions