Program to sort only positive numbers of the array

An algorithm to sort only the positive numbers of the given array without changing the positions of negative numbers.

Example

Input:
[ 2, -6, -3, -8, 4, 1]
[ 9, -2, 3, -1, 1, 5]

Output:
[1, -6, -3, -8, 2, 4]
[1, -2, 3, -1, 5, 9]

Using brute force approach to sort only positive numbers in the array

• We will first filter out the positive numbers from the given array and sort them in required order.
• After that we will use a temp array to store the sorted array and extra variable to track the elements of the filtered and sorted positive array.
• We will then iterate each element of the original array and check if it is positive or not.
• If it is positive then replace it with element from filtered positive array and add it to the temp array, else add the original negative element to the temp array.

We will be using filter() and sort() method of array to ease our work.

let sortOnlyPositive = (arr) => {
  //Filter the positive number from the array
  //And sort them
  let filtered = arr.filter(e => e > 0).sort();
  
  //Temp array to hold the sorted array
  let sorted = [];
  
  //To keep track of the positive sorted array list.
  let j = 0; 
  
  //Replace the positive numbers with sorted numbers
  for(let i = 0; i < arr.length; i++){
    //If the number is positive
    //Then replace it with first number
    //From filtered and sorted positive numbers array
    if(arr[i] > 0){
      sorted.push(temp[j++]);
    }else{
      //Else push the negative number at the same place
      sorted.push(arr[i]);
    }
  }
  
  //Return the temp array
  return sorted;
}

Input:
console.log(sortOnlyPositive([ 2, -6, -3, -8, 4, 1]));
console.log(sortOnlyPositive([ 9, -2, 3, -1, 1, 5]));

Output:
[1, -6, -3, -8, 2, 4]
[1, -2, 3, -1, 5, 9]

Time complexity: O(n + nlogn + n) = O(nlogn).
Space complexity: O(n).

Time and Space complexity

• It will take O(n) to filter the positive elements from the array and O(nlogn) to sort this filtered array, then to replace the elements it will take O(n), so Time complexity is O(n + nlogn + n) = O(2n + nlogn) = O(nlogn).
• It will take O(n) space to store the filtered positive numbers from the array and O(n) to store the sorted array, so Space complexity O(n + n) = O(n).