How to sort only part of array? between given indexes

Question

I have an array of numbers and I need to sort only part of it by left and right barriers. Can you please help me how to implement it correctly?

const sortBetween = (arr, left, right) => {
   ...
}
given: [9,3,5,7,4,9,4,1] , left = 2, right = 5
expected: [9,3,4,5,7,9,4,1]

[9,3,5,7,4,9,4,1] -> [9,3,4,5,7,9,4,1]

Thanks for the help.

This question looks like homework/interview-prep. Please check the help section on how to ask those type of question, specifically: "Questions asking for homework help must include a summary of the work you've done so far to solve the problem, and a description of the difficulty you are having solving it." — puelo, Jul 11 '20 at 13:42
Does this answer your question? [How to sort a part of an array with javascript?](https://stackoverflow.com/questions/36294175/how-to-sort-a-part-of-an-array-with-javascript) — user120242, Jul 11 '20 at 15:04
I would say divide it into 3 arrays, then take it from there... — Rick, Jul 11 '20 at 15:29

Nina Scholz · Accepted Answer · 2020-07-14T16:41:40.533

3

This is an approach by using sort directly, but shaping the access with a Proxy for length and the indices.

  type        original array       length
-------  ------------------------  ------
values    9  3  5  7  4  9  4  1       8
indices   0  1  2  3  4  5  6  7
-------  ------------------------  ------

  type          proxy view         length
-------  ------------------------  ------
values          5  7  4  9             4
indices         0  1  2  3
-------  ------------------------  ------

const
    sortBetween = (array, left, right) => {
        new Proxy(array, {
            get (target, prop) {
                if (isFinite(prop)) return target[+prop + left];
                if (prop === 'length') return right - left + 1;
                return target[prop];
            },
            set (target, prop, receiver) {
                target[+prop + left] = receiver;
                return true;
            }
        })
        .sort((a, b) => a - b);

        return array;
    };    
    
console.log(...sortBetween([9, 3, 5, 7, 0, 9, 4, 1], 2, 5)); // [9, 3, 0, 5, 7, 9, 4, 1]

edited Jul 14 '20 at 16:41

answered Jul 11 '20 at 15:42

Nina Scholz

376,160
25
347
392

1

nice interesting (and educationally valuable) approach. is there any benefit to doing it this way? I'm guessing it'd only have a performance advantage if you used generators and very large arrays? native level memcpy, malloc, and ptr optimizations would probably make the overhead of using Proxy undermine performance, so not even on a micro-opt level does it have an advantage. code elegance wise it's definitely a bit overcomplicated. – user120242 Jul 11 '20 at 16:29
1

the idea was not to slice or splice a part of the array and reassign the values to the array. But taking the original array and apply the sorting to it. and yes it's more educational then perfomance wise, because of the doubled access to a value. i was allways thinking about sorting kind of directly the array, but it is not possible to sort an array and omit some indices. – Nina Scholz Jul 11 '20 at 16:57
Note for performance advantage: For large arrays (and unbounded iterations), this approach significantly outperforms the other approaches. Biggest bottleneck is array copy (I underestimated its impact, and overestimated the memcpy optimizations). Difference is especially serious under Firefox. (Very) naive benchmark here: https://jsben.ch/licq4 @NinaScholz I think it may be important to note that this mutates in-place (which can be trivially changed, but significantly contributes to the difference) – user120242 Jul 11 '20 at 18:30
@NinaScholz There is an error if one of the array numbers is zero. – Michael Goldenberg Jul 14 '20 at 16:24
1

@MichaelGoldenberg, right, it was the wrong return value for `set`. it needs to return a truthy value for finishing a successfull operation. – Nina Scholz Jul 14 '20 at 16:42

iAmOren · Answer 2 · 2020-07-11T15:44:52.677

Final (I hope):

newArr = [].concat(
  arr.slice(0,left),
  arr.slice(left,right+1).sort(),
  arr.slice(right+1,arr.length)
)

taking right inclusively,
assuming left is not greater than right,
assuming the array is not empty,
etc.

Previous Edit:
I've read the comments.
Mostly correct.
The problem I oversaw was that the sort requested is between left and right inclusively, whereas slice's first argument is inclusive and second argument is exclusive.

I see, now, the last part should be an negative value, the difference between left and the array's length.
But, I'm not going to try to resolve that...

My original "answer":
I suggest you split the array into 3 sub-arrays using slice, sort the middle, and then put them back together using concat, such as so:

newArr=[].concat(arr.slice(0,left),arr.slice(left,right+1).sort(),arr.slice(left+right-1))

May I suggest you get more familiar with slice and concat by searching the web?

what if `right` is greater than `arr.length-1`, of `left` if greater than `right` ? So wrong answer for me !! — A.RAZIK, Jul 11 '20 at 14:05

score 1 · Answer 3 · answered Jul 11 '20 at 13:49

You can do it by using the Divide and Conquer method. You can try this-

const sortBetween = (arr, left, right) => {
  let leftArr = [],
    rightArr = [],
    sortedArr = [];
    
  /**
   * Divide the array into 3 parts. Left, Mid, Right.
   * You have to sort the mid one.
   */
  
  if (left > 0) {
     leftArr = arr.slice(0, left);
  }
  
  if (right < arr.length) {
    rightArr = arr.slice(right);
  }
  
  sortedArr = arr.slice(left, right).sort();
  
  // Finally merge the 3 parts and returns
  return [...leftArr, ...sortedArr, ...rightArr];
}

const arr = [9,3,5,7,4,9,4,1];

const res = sortBetween(arr, 2, 5);
const res1 = sortBetween(arr, 0, 5);
const res2 = sortBetween(arr, 0, 8);

console.log(res, res1, res2);

.as-console-wrapper {min-height: 100%!important; top: 0}

How to sort only part of array? between given indexes

3 Answers3

Linked