CODEWITHSUNDEEP
algorithmsorting
ryeguy
ryeguy

Reputation: 66861

How to quickly resort a list with only one changed value?

Let's say I have a list of objects that are sorted by a specific field on that object. If one of the objects changes that property, its position in the sorted list would need to be updated.

What sorting algorithm or "tricks" could I use to very quickly sort this list, given that it falls out of sort only one item at a time?

The data structure is an array, and I have direct access to the index of the changed item.

I am using Scala for this, but any general tips or pointers would be helpful too.

Upvotes: 7

Views: 2099

Answers (7)

Bart Kiers
Bart Kiers

Reputation: 170247

If the list is sorted, you can simply remove the element you're about to change from the list, and after changing it, you could "binary-insert" it, no? That would take an average of log(n) steps.

If you can, change from an array to a java.util.TreeMap: both removal and insertion will be log(n) operations: which will be faster than your O(1) access + O(n) re-insertion solution using an array.

Upvotes: 8

Joren
Joren

Reputation: 14746

For an array, inserting an element into the correct position would be O(n), because you need to copy the array elements to make room for an extra element. You could find the index you need to insert at by doing a binary search (O(log n)) or linear search (O(n)). Whatever choice you make, the algorithm as a whole will be O(n).

The only way to do this very quickly is to use a data structure that's better suited to this situation: a binary search tree. Insertion would be O(log n) if the tree remains decently balanced (Use a self-balancing binary search tree to ensure this, or hope your data will not be inserted in a highly regular order to approximate O(log n).)

O(log n) is way faster than O(n) for even moderately large lists, so if you have lists that may be nearly arbitrarily large and really care about sorting performance, use a binary search tree.

Upvotes: 1

MAK
MAK

Reputation: 26586

If the list is really big and there are a large number of update operations expected, a simple random access array or linked list will be too slow. If you use arrays/linked lists, each update operation will cost O(n). With small lists and/or small number of updates this is adequate.

For larger lists, you can achieve O(log(n)) updates by using a sorted O(log(n)) data structure (AVL/RB-trees, Skip-Lists,segment trees etc.). A simple implementation can involve removing the element to be updated, changing the value and then reinserting it. Many popular languages have some sort of sorted data structure in their library (e.g. TreeMap/TreeSet in Java, multiset/multimap in C++'s STL), or you can easily find a free implementation for your language.

Upvotes: 2

Lasse V. Karlsen
Lasse V. Karlsen

Reputation: 391506

Depending on whether the new value is larger than, or smaller than, the previous one, you could "bubble" it in place.

The pseudo-code would look something like this:

if new value larger than old value
    then if new value is larger than next value in collection
        then swap the value with the next value
        iterate until value is not larger than next value
else if new value is smaller than previous value in collection
    then swap the value with the previous value
    iterate until value is not smaller than the previous value

Of course, a better way would be to use binary search.

First, locate the new spot in the collection where the element should be. Then, shift elements into place. If the new spot index is greater than the current spot index, you shift elements down one element, otherwise you shift them up. You shift elements starting from the spot you previously occupied, to the one you want to occupy. Then you store the value into the spot you found.

For instance, assume this collection:

 a   b   c   d   e   f   g   h   i    j
10  20  30  40  50  60  70  80  90  100

Then you want to change the value of the f element from 60 to 95.

First you figure out where it should be. Using binary search, we found that it should be between 90 and 100:

 a   b   c   d   e   f   g   h   i    j
10  20  30  40  50  60  70  80  90  100
                                   ^
                                   +- here

Then you shift elements from the current position down one element, like this:

 a   b   c   d   e   f   g   h   i    j
10  20  30  40  50  60  70  80  90  100  <-- from this
10  20  30  40  50  70  80  90  ??  100  <-- to this

And then you store the value into the ?? space, which gives you this formation

 a   b   c   d   e   g   h   i   f    j
10  20  30  40  50  70  80  90  95  100

Upvotes: 2

Russell Steen
Russell Steen

Reputation: 6612

Remove the one item, and re-add it into the correct position. IF you are only doing one item, your max run-time is N.

If you are doing more than one, you should wait till they are all done and then resort. But you'll need to tell us a lot more about your problem space. Quick is contrained by memory and other factors which you'll need to determine to pick the right algorithm.

Upvotes: 0

user180100
user180100

Reputation:

Moving the unsorted element to left or right in the list seems the optimal solution

Upvotes: 1

levik
levik

Reputation: 117569

You could just do one iteration of bubble sort: start from the beginning of the list, and iterate until you find the out of order element. Then move it in the appropriate direction until it falls in place. This will give you at worst 2N performance.

Upvotes: 0

Related Questions