Learning Journal

1/24/2024

Relative Sort Array

Tags: algorithms leetcode selection_sort

function relativeSortArray(arr1: number[], arr2: number[]): number[] {

    let curP = 0;

  for(let i2 = 0; i2 < arr2.length; i2++) {
      const curNum2 = arr2[i2];

      for(let i1 = 0; i1 < arr1.length; i1++) {
          if(arr1[i1] === curNum2){
            const temp = arr1[i1];
            arr1[i1] = arr1[curP];
            arr1[curP] = temp;
            curP++;             
          }
      }
  }  

  if(curP < arr1.length){
      for(let i = curP; i < arr1.length; i++) {
          let min = arr1[i]; 
          let minI = i;

          for(let j = i  + 1; j < arr1.length; j++) {
              if(arr1[j] < min){
                  minI = j;
                  min = arr1[j];
              }
          }

          if(arr1[i] > min) {
            arr1[minI] = arr1[i];
            arr1[i] = min;
          }

      }

    
  }

  return arr1;
};function relativeSortArray(arr1: number[], arr2: number[]): number[] {

    let curP = 0;

  for(let i2 = 0; i2 < arr2.length; i2++) {
      const curNum2 = arr2[i2];

      for(let i1 = 0; i1 < arr1.length; i1++) {
          if(arr1[i1] === curNum2){
            const temp = arr1[i1];
            arr1[i1] = arr1[curP];
            arr1[curP] = temp;
            curP++;             
          }
      }
  }  

  if(curP < arr1.length){
      for(let i = curP; i < arr1.length; i++) {
          let min = arr1[i]; 
          let minI = i;

          for(let j = i  + 1; j < arr1.length; j++) {
              if(arr1[j] < min){
                  minI = j;
                  min = arr1[j];
              }
          }

          if(arr1[i] > min) {
            arr1[minI] = arr1[i];
            arr1[i] = min;
          }

      }

    
  }

  return arr1;
};

This is my solution for the Relative Sort Array problem.

If you know the selection sort, it should be easy. Basically, you do selection sort twice. The first time, you do it to sort arr1 in the order dictated by arr2. Then, if some elements haven't been sorted, you do selection sort again, but this time, you sort it in ascending order.

To do selection sort on the first portion, you go over each item in the arr2 and find which items in arr1 that are equal to it, then put them one by one back to the arr1. How can you put them back?

Basically, you keep a pointer that initially points to the first element of the arr1; when you find an element that needs to be put back, you swap the element that the pointer currently points to with that element and move the pointer to the next item (similar to what you do in selection sort).