Sort array from bottom to top with lowest index of change

Question

I have an array of objects, each object has timestamp field. Now I'd like to sort this array starting from bottom to top by timestamp field, and as a result I need sorted array and also index of where below of it inclusively algorithm made changes.

Example:

Array = [
    {timestamp: 1},  //index 0
    {timestamp: 2},  //index 1
    {timestamp: 3},  //index 2 
    {timestamp: 4},  //index 3
    {timestamp: 5},  //index 4
    {timestamp: 6},  //index 5
    {timestamp: 10}, //index 6
    {timestamp: 8},  //index 7
    {timestamp: 9},  //index 8
    {timestamp: 7}   //index 9
];

const result = magicSort(array);

result.array == [
    {timestamp: 1},
    {timestamp: 2},
    {timestamp: 3},
    {timestamp: 4},
    {timestamp: 5},
    {timestamp: 6},
    {timestamp: 7},
    {timestamp: 8},
    {timestamp: 9},
    {timestamp: 10}
];

result.changesMadeFromIndexToEnd == 6

How can I do this?

Have a look at this question. It should answer yours https://stackoverflow.com/questions/1129216/sort-array-of-objects-by-string-property-value — Thakkie, Dec 03 '20 at 13:36
@NinaScholz Sorry but u havent read whole question. Sorting is easy, but I need additional output of from where (index) changes were made — ElSajko, Dec 03 '20 at 13:38
I don’t think trying to cram this into any sort algorithm itself makes much sense to begin with; I would just sort, and then loop over original and sorted array after, until I find the first different item. — CBroe, Dec 03 '20 at 13:39
@CBroe sounds good but also like wasting performance, I was wondering if there is algorithm that may do both task at the same time to save power — ElSajko, Dec 03 '20 at 13:40
@NinaScholz I think that is the other way around. They don’t want to sort only part of an array here, but they want to figure out how much of the original array (from the beginning) was “kept” as-is. — CBroe, Dec 03 '20 at 13:40
@NinaScholz please reopen it, you misunderstood the question without reading it completely — ElSajko, Dec 03 '20 at 13:43
@NinaScholz I've asked about known techniques for achieving results, the most important part is about that `index` that tells you from where array have changed. CBroe got it right, but I'm looking for a way to do both task at the same time, coz it will be more perfromance saving. — ElSajko, Dec 03 '20 at 13:47
_“I was wondering if there is algorithm that may do both task at the same time to save power”_ - this is a very special requirement, that probably > 99.999% of cases where something needs to be sorted, won’t ever need - so I don’t think you will find it in any existing implementation. Not saying that this could not probably done, when you implement a sort algorithm yourself, but to have this “built-in” to standard sort functionality, would be a performance _drain_ on the majority of use cases. — CBroe, Dec 03 '20 at 13:49
@CBroe, you can put an answer with this idea of sorting and looping through both arrays to find the index — ElSajko, Dec 03 '20 at 13:50

score 2 · Accepted Answer · answered Dec 03 '20 at 13:55

This is a rather special requirement, that probably > 99% of cases where something needs to be sorted, won’t ever need - so I don’t think you will find it in any existing implementation. Not saying that this could not probably done, when you implement a sort algorithm yourself, but to have this “built-in” to standard sort functionality, would be a performance drain on the majority of use cases that don’t need it.

I would just sort the array first, and then loop over original and sorted array after, until I find the first different item.
How good or bad that will do in terms of performance, really depends on the size of your data set. If it gets too slow, you could still try a divide & conquer approach here: Check the elements in the middle of both arrays first - if those are still the same, continue searching the same way in the second half, if not, in the first.

score 1 · Answer 2 · answered Dec 03 '20 at 13:37

1

Hi this is pretty straight forward using the sort function:

const magicSort = (array) => 
  array.sort((a,b) => (a.timestamp > b.timestamp) ? 1 : -1)

answered Dec 03 '20 at 13:37

Bastian E.

408
2
11

Sorry but u havent read whole question. Sorting is easy, but I need additional output of from where (index) changes were made – ElSajko Dec 03 '20 at 13:38

Sort array from bottom to top with lowest index of change

2 Answers2