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.
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.
Moving the unsorted element to left or right in the list seems the optimal solution
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.
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.
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
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.
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.