-1

in this algorithm

let arr =[8,10,222,36,5,0,0];

let insertionSort = (arr) => {
    let len = arr.length;
    for(let i = 0; i < len; i++){
        let curr = arr[i];
        let j = i - 1;
        while(arr[j] > curr){ 
            arr[j+1] = arr[j];
            j--
        };
        j++
        arr[j] = curr;
    };
    console.log(arr);
};

insertionSort(arr);

why the j-- and j++

I mean what they do exactly? , why we use them? (I understand evreything else this)

what they exactly do in the array ? change the position of numbers ? or what.

Rabie
  • 49
  • 7
  • https://www.geeksforgeeks.org/insertion-sort/ You are moving the items so you need to shift down – epascarello Jul 08 '21 at 17:18
  • https://www.toptal.com/developers/sorting-algorithms – epascarello Jul 08 '21 at 17:23
  • sorry , but can you explain how exactly ? – Rabie Jul 08 '21 at 17:25
  • It is explaining the algorothm. You take a card, and you go down the deck until it fits in the correct place (j--). Once you find the right spot it puts it into the right spot. The visualizations show it. – epascarello Jul 08 '21 at 17:29
  • See [What does this symbol mean in JavaScript?](/q/9549780/4642212) and the documentation on MDN about [expressions and operators](//developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators) and [statements](//developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements). – Sebastian Simon Jul 08 '21 at 17:29
  • @SebastianSimon WRONG, The question is about logic, not the operators. – epascarello Jul 08 '21 at 17:30
  • This question is not about the operators... lol, reopened. – epascarello Jul 08 '21 at 17:32
  • 2
    *"I mean what they do exactly?"*: I rest my case... OP should really focus on a clear, single question. – trincot Jul 08 '21 at 17:35
  • @epascarello How is suggesting to read the documentation that answers the question “I mean what they do exactly?” _“WRONG”_? What exactly is wrong there? There isn’t even a factual statement there that could be either wrong or right. – Sebastian Simon Jul 08 '21 at 17:43
  • The question is asking about how the alogorithm works, it is not how the operators work. – epascarello Jul 08 '21 at 17:44
  • @epascarello You already said that, to which trincot replied with their comment. – Sebastian Simon Jul 08 '21 at 17:45

3 Answers3

3

j++ is for incrementing, j-- is for decrementing :

for(let i = 0; i < len; i++)

→here you read through your array - from the first item (i = 0) to the last item (i = len)

    let curr = arr[i];
    let j = i - 1;
    while(arr[j] > curr){ 
        arr[j+1] = arr[j];
        j--
    };
    j++
    arr[j] = curr;

→Let say you have a subarray arr[0..i]. here you go through your subarray, in the inverse order. Each time than a item is higher than arr[i], it takes the value of its predecessor. It makes all the value shift from one rank to the right of the array. When the while loop stops, the item on position j in the array takes the value of current, by this operation you make sure that you have moved the arr[i] value inside the arr[0..i] subarray, making sure that items are sorted inside this subarray.

Just remember that an invariant in the upper for loop is that arr[0..i] is sorted. When you increment i and go through a new iteration inside your for loop with the subarray arr[0..i], the curr value can be anything, but the values arr[0..i-1] are sorted, so the nested while loop make sure that the curr value is inserted where it should.

for instance, let's take your array [8,10,222,36,5,0,0]. with i = 4 :

curr = 36
arr[0..i] = [8,10,222,36]
#iteration of the while loop : 
    j=3: arr[j]=222>curr -> arr[0..i]=[8,10,222,222]
    j=2: arr[j]=10<curr -> end of the while loop
    (arr[j+1] = curr) -> arr[0..i] = [8,10,36,222]
arr[0..4] is sorted
Godev
  • 316
  • 1
  • 4
  • 12
2

The algorithm is like taking a deck of of cards. You are sorting them one at a time by taking the card and you check to se if the one before it is greater than the one you have. You than check the one before that and that until you find the right spot.

So the j-- is the part where you are checking each card before the one you have. You are shifting all of the cards up one to the spot to fill the void of pulling out the card.

Once you find the spot the j++ is to fill the current void with the card in your hand.

Grab the current index
         V
1,2,4,5,[3]

Look at 5. Is it greater than 3? Yes, move 5 up
       V
1,2,4,[5],5
j--

Look at 4. Is it greater than 3? Yes, Move 4 up
1,2,[4],4,5
j--

Look at 2. Is it greater than 3? NO, leave the 2 alone

Now we are at the "2" so add one to get to the index where 3 needs to live.
j++
1,2,[3],4,5
epascarello
  • 204,599
  • 20
  • 195
  • 236
0

To clarify: these operators originate in the "C" language.

i++ is a post-increment operator which returns the present value of i and then increments it.

++i is a pre-increment operator which increments the value of i then returns the incremented value.

Nearly every programming language since then has copied these very-handy constructs.

Mike Robinson
  • 8,490
  • 5
  • 28
  • 41