Menu
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.
290
Use the Python List sort() method to sort a list in place. The sort() method sorts the string elements in alphabetical order and sorts the numeric elements from smallest to largest. Use the sort(reverse=True) to reverse the default sort order.
If you want to create a new sorted list without modifying the original one, you should use the sorted function instead. As you can notice, both sort and sorted sort items in an ascending order by default.
Use a lambda function with a tuple to sort with two keys Call sorted(iterable, key: NoneType=None) with a collection as iterable . For key , create a lambda function that takes an element as a parameter and returns a 2-tuple of mapped to values.
Approach : Zip the two lists. Create a new, sorted list based on the zip using sorted(). Using a list comprehension extract the first elements of each pair from the sorted, zipped list.
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.
152
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 you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
