0
$\begingroup$

I'm thinking how I can insert an element into an ordered array. Assume the array has a capacity for one element. I've implemented two methods.

The one finds the position to insert, moves elements one position to the right and inserts the element into the position.

The seconds one which seems more intuitive to me is to put an element into the last position in an array and then put it in the correct position by swapping with the left element - the way it's done in the insertion sort.

However, I googled for the solution and almost all suggestions are some modification of the first algorithm. So I'm wondering if there's something I'm missing. Can you guys please help?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Both work. Both approaches are approximately equivalent, in some sense. However, your approach will do about twice as much work.

Think about an array that initially contains $[2,4,6,8,0]$ where the $0$ is the final empty element that can be filled in. Imagine you want to insert the number $5$.

  • The standard method will read $8$ from index $3$, then write $8$ to index $4$, yielding $[2,4,6,8,8]$; then read $6$ from index $2$ and write $6$ to index $3$, yielding $[2,4,6,6,8]$; then write $5$ to index $2$, yielding $[2,4,5,6,8]$. That's 2 reads and 3 writes -- 5 memory operations.

  • Your method will swap $8$ and $0$, yielding $[2,4,6,0,8]$ (this involves reading $8$ from index $3$, reading $0$ from index $4$, writing $8$ to index $4$, writing $0$ to index $3$); then swap $6$ and $0$, yielding $[2,4,0,6,8]$; then overwrite the $0$ with $5$. Each swap requires 2 reads and 2 writes, so this does a total of 4 reads and 5 writes -- 9 memory operations. That's about twice as much.

Why is your method slower? Because your method keeps reading the $0$ and writing it somewhere. That is extra, unnecessary work. If you care about optimization, that might matter. If you just want a method that you can understand, either one should be fine.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks, That's 2 reads and 3 writes -- 5 memory operations. - yeah, but it has to find the position first, so it's additional reads and compares, no? $\endgroup$
    – Max Koretskyi
    Commented May 18, 2017 at 16:36
  • $\begingroup$ @Maximus, I guess the best way to compare their performance is to implement it and see. I wouldn't put too much faith into my count of memory operations. That said, I expect that finding the position will be done with binary search, which takes only $O(\lg n)$ time, and thus will be negligible compared to the cost of shifting array elements around, when the array is large... but if you really care, implement and see what happens. Don't take my operation counts too seriously -- they're just intended to give some intuition about what might happen. $\endgroup$
    – D.W. ♦
    Commented May 18, 2017 at 17:23
  • 1
    $\begingroup$ thus will be negligible compared to the cost of shifting array elements around, when the array is large - yeah, that's my point, moving n elements to the right is almost the same as swapping n elements, but in the first case we also have to first find the index to insert into $\endgroup$
    – Max Koretskyi
    Commented May 19, 2017 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.