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

Question

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!

Your guess is correct. Also, that's a wasteful implementation of a not-very-good algorithm, it's unfortunate that it's from an educational resource. — Pointy
– Pointy, Commented Jan 22, 2020 at 16:02
Using .splice() adds an extra inefficiency, as that requires copying the tail end of the source array each time. — Pointy
– Pointy, Commented Jan 22, 2020 at 16:07
How would you write a function to remove an element from the middle of an array? You have to copy every element from that position back one position. That's an O(n) process. — Pointy
– Pointy, Commented Jan 22, 2020 at 16:11
@Pointy Using selection sort adds inefficiency, because it's an O(n^2) algorithm where an O(n log n) algorithm could solve the same problem. The particular way of implementing selection sort is not so important, and I guess this is just for a learning exercise. — kaya3
– kaya3, Commented Jan 22, 2020 at 16:14
@kaya3 I know that, but it's from a textbook. There's no reason to teach people questionable coding practices. — Pointy
– Pointy, Commented Jan 22, 2020 at 16:22

kaya3 · Accepted Answer · 2020-01-22 16:17:52Z

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.

2 revs · Accepted Answer · 2020-01-22 16:30:30Z

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.

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related