3
\$\begingroup\$

I wrote a simple sort algorithm in JavaScript, but code climate is complaining its complexity being too high (currently sitting on 6 instead of 5, which is code climate wants).

I personally cannot see how it can be further simplified.

Can anyone help? The following algorithm sorts an array of numbers from largest to smallest.

function selectionSort(array) {
    let index = 0;
    let terminatingIndex = array.length - 1;
    let nextElementIndex = null;

    while (index < terminatingIndex) {
        nextElementIndex = index + 1;
        while (nextElementIndex <= terminatingIndex) {
            if (array[index] < array[nextElementIndex]) {
                [array[index], array[nextElementIndex]] = [array[nextElementIndex], array[index]];
            }
            nextElementIndex++;
        }
        index++;
    }
    console.log(`The sorted array is: ${array}`);
}
\$\endgroup\$
2
\$\begingroup\$

I think the problem could be, that your algorithm isn't exactly a selection sort but rater a bubble sort. They are very similar, but where bubble sort swaps every two elements when the left is smaller than the right (descending order), selection sort defers swapping to after the inner loop is finished and then only swaps the last found candidate with the index'th element.

To accomplish that in your algorithm, you can modify it as follows:

function selectionSort(array) {
  let index = 0;
  let length = array.length;
  let nextElementIndex = 0;

  while (index < length - 1) {
    nextElementIndex = index + 1;

    let maxIndex = index; // This will hold the index of the possible last candidate for swapping.

    while (nextElementIndex < length) {
      if (array[maxIndex ] < array[nextElementIndex]) {
        // Instead of swapping here, only the index of the candidate is saved.
        maxIndex = nextElementIndex;
      }
      nextElementIndex++;
    }

    // And finally: if any element to the right of index is greater than the element at index then swap.
    if (maxIndex != index) {
      [array[index], array[maxIndex ]] = [array[maxIndex ], array[index]];
    }

    index++;
  }
}

A suggestion that may improve readability could be to use for-loops instead of while -loops

\$\endgroup\$
  • 2
    \$\begingroup\$ Thanks for this, you were right, I mixed up bubble sorting and selection sorting. \$\endgroup\$ – Yu Zhang Aug 11 at 21:30
2
\$\begingroup\$

Another solution is to use the sort function of javascript. I recommend this solution for simplicity and readability

var array1 = [1, 30, 4, 21, 100000];
array1.sort(() => {
  return b - a 
});
console.log(array1) // [100000, 30, 21, 4, 1]

See the docs for more informations : https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

Have a nice day !

\$\endgroup\$
  • 2
    \$\begingroup\$ Does this built-in method use selection sorting? If so, I would deem this answer valid, since the OP did not specify 'reinventing-the-wheel'. \$\endgroup\$ – dfhwze Aug 12 at 9:36
  • \$\begingroup\$ thanks, I had known this approach, but did not use it as I was building something from scratch. But I would definitely use this approach otherwise. \$\endgroup\$ – Yu Zhang Aug 12 at 21:41
  • 1
    \$\begingroup\$ @dfhwze The specification does not require a certain sorting method, so it depends on which JavaScript engine is used. \$\endgroup\$ – Kruga Aug 14 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.