30
$\begingroup$

What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)?

I was thinking something along the following lines.

I could add to the end of an array and then use bubblesort as it has a best case (totally sorted array at start) that is close to this, and has linear running time (in the best case).

On the other hand, if I know that I start out with a sorted array, I can use a binary search to find out the insertion point for a given element.

My hunch is that the second way is nearly optimal, but curious to see what is out there.

How can this best be done?

$\endgroup$
  • 1
    $\begingroup$ The fastest way, if you have to do it often, is not to use an array in the first place. $\endgroup$ – reinierpost Apr 3 '12 at 11:49
  • $\begingroup$ Self balancing binary tree you mean? $\endgroup$ – soandos Apr 3 '12 at 14:34
  • $\begingroup$ Yes, possibly; see the answers ... $\endgroup$ – reinierpost Apr 4 '12 at 7:35
24
$\begingroup$

We count the number of array element reads and writes. To do bubble sort, you need $1 + 4n$ accesses (the initial write to the end, then, in the worst case, two reads and two writes to do $n$ swaps). To do the binary search, we need $2\log n + 2n + 1$ ($2\log n$ for binary search, then, in the worst case, $2n$ to shift the array elements to the right, then 1 to write the array element to its proper position).

So both methods have the same complexity for array implementations, but the binary search method requires fewer array accesses in the long run... asymptotically, half as many. There are other factors at play, naturally.

Actually, you could use better implementations and only count actual array accesses (not accesses to the element to be inserted). You could do $2n + 1$ for bubble sort, and $\log n + 2n + 1$ for binary search... so if register/cache access is cheap and array access is expensive, searching from the end and shifting along the way (smarter bubble sort for insertion) could be better, though not asymptotically so.

A better solution might involve using a different data structure. Arrays give you O(1) accesses (random access), but insertions and deletions might cost. A hash table could have O(1) insertions & deletions, accesses would cost. Other options include BSTs and heaps, etc. It could be worth considering your application's usage needs for insertion, deletion and access, and choose a more specialized structure.

Note also that if you want to add $m$ elements to a sorted array of $n$ elements, a good idea might be to efficiently sort the $m$ items, then merge the two arrays; also, sorted arrays can be built efficiently using e.g. heaps (heap sort).

$\endgroup$
  • 1
    $\begingroup$ "A hash table could have O(1) insertions & deletions" -- amortised, usually. $\endgroup$ – Raphael Apr 1 '12 at 7:05
  • 8
    $\begingroup$ Amortized expected. $\endgroup$ – JeffE Apr 2 '12 at 7:28
  • $\begingroup$ BST has $O(log\ n)$ for search and insert (wikipedia), so why is it not top recommended choice here? $O(2\ log\ n)$ to search and insert. $\endgroup$ – Kashyap Jun 4 at 17:00
7
$\begingroup$

If you have any reason for not using heap, consider using Insertion Sort instead of Bubble Sort. It's better when you have a few unsorted elements.

$\endgroup$
7
$\begingroup$

Because you are using an array, it costs $O(n)$ to insert an item - when you add something to the middle of an array, for example, you have to shift all of the elements after it by one so that the array remains sorted.

The fastest way to find out where to put the item is like you mentioned, a binary search, which is $O(\lg n)$, so the total complexity is going to be $O(n + \lg n)$, which is on the order of $O(n)$.

That being said, if I felt particularly snarky, I could argue that you can "add to a sorted array" in $O(1)$, simply by slapping it to the end of the array, since the description doesn't indicate that the array has to remain sorted after inserting the new element.

Anyway, I don't see any reason to pull bubble sort out for this problem.

$\endgroup$
  • 2
    $\begingroup$ It is not very useful to remain at $\mathcal{O}$-level when comparing algorithms that all take linear time. $\endgroup$ – Raphael Apr 1 '12 at 7:06
  • $\begingroup$ +1 for being snarky.. :-) $\endgroup$ – Kashyap Jun 4 at 16:50
4
$\begingroup$

Patrick87 explained this all very well. But one additional optimization you could make would be to use something like a circular buffer: you can move items right of the position of the inserted element to the right, as usual. But you can also move items to the left of the correct position to the left. To do this, you need to treat the array as circular, i.e. the last item is right before the first one and it also requires you to keep the index where the items currently start.

If you do this, it could mean you make about half as many array accesses (assuming uniform distribution of indexes you insert to). In the case of doing binary search to find the position, it's trivial to choose whether to shift to the left or to the right. In the case of bubble sort, you need to “guess” correctly before starting. But doing that is simple: just compare the inserted item with the median of the array, which can be done in single array access.

$\endgroup$
4
$\begingroup$

I have used the Insertion sort algorithm effectively for this issue. At one time we had a performance issue with a hash table object, I wrote a new object that used binary search instead that increased performance significantly. To keep the list sorted it would keep track of the number of items added since the last sort (i.e. number of unsorted items,) when the list needed to be sorted due to a search request, it performed an insertion sort or a quick sort depending on the percentage of items unsorted. Use of the insertion sort was key in improving the performance.

$\endgroup$
  • $\begingroup$ Do you have a formal result regarding amortised operation costs? And: welcome! $\endgroup$ – Raphael Apr 6 '12 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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