CODEWITHSUNDEEP
javascriptarraysalgorithmselection-sort
Code Eagle
Code Eagle

Reputation: 1242

Why should length of the array be stored in selection sort algorithm?

The algorithm code from Grokking algorithm book:

const findSmallestIndex = (array) => {
  let smallestElement = array[0]; // Stores the smallest value
  let smallestIndex = 0; // Stores the index of the smallest value

  for (let i = 1; i < array.length; i++) {
    if (array[i] < smallestElement) {
      smallestElement = array[i];
      smallestIndex = i;
    }
  }

  return smallestIndex;
};

// 2. Sorts the array
const selectionSort = (array) => {
  const sortedArray = [];
  const length = array.length;

  for (let i = 0; i < length; i++) {
    // Finds the smallest element in the given array 
    const smallestIndex = findSmallestIndex(array);
    // Adds the smallest element to new array
    sortedArray.push(array.splice(smallestIndex, 1)[0]);
  }

  return sortedArray;
};

console.log(selectionSort([5, 3, 6, 2, 10])); // [2, 3, 5, 6, 10]

The problem is in the function selectionSort, storing the array length in the variable wes necessary to make it work correctly and this one i couldn't understand, i tried to not store the length in a variable:

const selectionSort = (array) => {
  const sortedArray = [];


  for (let i = 0; i < array.length; i++) {
    // Finds the smallest element in the given array 
    const smallestIndex = findSmallestIndex(array);
    // Adds the smallest element to new array
    sortedArray.push(array.splice(smallestIndex, 1)[0]);
  }

  return sortedArray;
};

console.log(selectionSort([5, 3, 6, 2, 10])); // [2, 3, 5]

I guessed that the problem may be the splice method because it reduces the length every time in the loop but i think the index is not important here, so it may not be be the problem!

Upvotes: 1

Views: 227

Answers (2)

Pointy
Pointy

Reputation: 414086

I'm putting this here for the sole reason that the posted implementation, apparently from an algorithms text, is needlessly overcomplicated and inefficient as well.

function selectionSort(array) {
  function smallestIndex(start) {
    let si = start;
    for (let i = start + 1; i < array.length; ++i) {
      if (array[i] < array[si])
        si = i;
    }
    return si;
  }

  for (let i = 0; i < array.length; i++) {
    let index = smallestIndex(i), t;
    // swap value into current slot
    t = array[index];
    array[index] = array[i];
    array[i] = t;
  }
  return array;
}

Here, the smallestIndex() function is enhanced to take a starting position as a parameter. Thus it finds the index of the smallest value in the remainder of the array. On the first iteration, that'll be the smallest value in the whole array. That value is swapped with whatever is at the current starting point, so after that first time through the main loop position 0 in the array is the smallest value in the whole array.

On the next iteration, the search for the index starts at 1, so that process will find the second smallest value from the original array, and swap that into position 1.

The process continues through the array. Note that no new arrays are constructed, and there are no calls to linear-time Array methods.

Upvotes: 1

kaya3
kaya3

Reputation: 51162

Your code is removing the element from the original array, so on each iteration, i++ increases i and also splice decreases array.length. That means i and array.length get closer together by 2 each time instead of by 1, so the loop only iterates half as many times as you want it to. That means you only sort half of the elements into sortedArray.

By copying const length = array.length; first, the variable length is not changed inside the loop, so the i++ makes i closer to length on each iteration by 1, so the number of iterations is the original array length, and every element gets sorted.

As a side note, your algorithm sorts into a new array, but leaves the original array empty. That's probably never what you want; a sorting algorithm should either sort the array in-place (leaving the original array in sorted order), or return a new sorted array (leaving the original array unchanged). You could fix this by making a copy of array at the start of your function, so the algorithm destroys the copy instead of the original.

Upvotes: 2

Related Questions