Q: Hello, I having little trouble about implementing the selection sort var selectionSort = function(array) { var temp; for(var i = 1; i < array.length; i++){ // starting array iteration at index = 1 temp = indexOfMinimum(array,i); // to store value of minIndex if(array[temp] < array[i-1]){ // comparing the value at minIndex with element //present at i-1 //swap if value at minIndex less than value at i-1 swap(array, i-1,temp); } } }; even though the console shows the correct sorted array i cannot move to next step. I would like to know what is the bug in code. Thank you!

While it will sort the values correctly, it is a bit different from how selectionSort normally works. It is different enough that the grader doesn't think it is following the selectionSort algorithm. Normally in selection sort: - instead of starting at index 1 you would start at index 0. - you don't have to check the value of the minValue (array[temp] in your code) vs the value at the index, instead you just always swap the minValue and the value at the index (this will be safe if the range of values you previously checked for your minValue includes the value at the index ) Good Luck

Q: I'm sorry, I do not speak english, but If you have the array = [ 1, 1, 0, 2 ] and applying the algorithm as it says in the second paragraph, by analogy with the cards , as in the first iteration of the array would be ordered because it is : array = [0 , 1, 1 , 2] . Wonder is necessary to continue the algorithm until through all the indices in the subarray as paragraph 6 states or stopped in the first iteration .

With selection sort, you have to go through all the iterations (the algorithm has no way of knowing if the array is sorted before it has done all the iterations) . However, you could try to optimize the algorithm by checking to see if the array was sorted. To be able to skip future iterations once sorted, you would need to add a flag if an unsorted pair of neighbors was found, and then each pass, you would need to check, for each element whether each pair of neighbors was sorted. If not, the flag would be set to false. After each pass you could check the flag. If the flag was true, then you could skip the future iterations since the array was sorted. This optimization is often incorporated into bubble sort which compares neighbors anyhow ( bubble sort is O(n^2) but generally performs worse than the other O(n^2) sorting algorithms). The problem with adding this check to selection sort is it adds an additional comparison, which would make the algorithm slower for arrays which are not nearly sorted. That being said, if you thought you were going to be sorting a lot of arrays that were nearly sorted, then you should just use insertion sort, which performs very well with nearly sorted arrays. Hope this makes sense

Q: I fail to see why this doesn't work :( for (var i = minIndex + 1; i === array.length - 1; i++) { if (min(minValue, array[i]) < minValue) { minIndex = i; minValue = array[i]; } }

There's a couple of issues: 1) Suppose we call: `indexOfMinimum([2,9,1],0)` The first time the for loop executes: What is the value of `i` ? What is the value of `array.length` ? Is `i === array.length-1` true or false ? That should show the first problem. 2) - You shouldn't need to call the min function, in the condition of your if statement. You should be able to simplify that condition. Good Luck

Q: In the challenge implement selection sort I had the code `var swap = function(array, firstIndex, secondIndex) { var temp = array[firstIndex]; array[firstIndex] = array[secondIndex]; array[secondIndex] = temp; }; var indexOfMinimum = function(array, startIndex) { var minValue = array[startIndex]; var minIndex = startIndex; for(var i = minIndex + 1; i < array.length; i++) { if(array[i] < minValue) { minIndex = i; minValue = array[i]; } } return minIndex; }; var selectionSort = function(array) { var MinIndex; for(var StartingIndex;StartingIndex<array.length;StartingIndex++ ) { MinIndex = indexOfMinimum(array,StartingIndex); swap(array, StartingIndex, MinIndex); } }; var array = [22, 11, 99, 88, 9, 7, 42]; selectionSort(array); println("Array after sorting: " + array); Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);` The Program.assertEqual said that my code was wrong. I don't know why the function selectionSort isn't working. Can you help me?

`StartingIndex` isn't initialized to any value, so it is `null` (which is an invalid input to the `indexOfMinimum` function). As a side note, the general convention in JavaScript for variable names is camel case with the initial letter in lower case i.e. `startingIndex` instead of `StartingIndex`. It won't impact how your code works, but it will make it easier for others to read your code if you follow the convention.

Question 1

I don,'t know javascript shall i stop the course here learn javascript then resume it

Accepted Answer

You should start here: https://www.khanacademy.org/computing/computer-programming

Question 2

Hello,
I having little trouble about implementing the selection sort
var selectionSort = function(array) {
    var temp;                                                            
    for(var i = 1; i < array.length; i++){          // starting array iteration at index = 1
            temp = indexOfMinimum(array,i); // to store value of minIndex  
            if(array[temp] < array[i-1]){               // comparing the value at minIndex with element //present at i-1
//swap if value at minIndex less than value at i-1
                swap(array, i-1,temp);
            }
        }
};

even though the console shows the correct sorted array i cannot move to next step.

I would like to know what is the bug in code.
Thank you!

Accepted Answer

While it will sort the values correctly, it is a bit different from how selectionSort normally works. It is different enough that the grader doesn't think it is following the selectionSort algorithm.

Normally in selection sort:
- instead of starting at index 1 you would start at index 0.
- you don't have to check the value of the minValue (array[temp] in your code) vs the value at the index, instead you just always swap the minValue and the value at the index (this will be safe if the range of values you previously checked for your minValue includes the value at the index )

Good Luck

Question 3

I'm sorry, I do not speak english, but
If you have the array = [ 1, 1, 0, 2 ] and applying the algorithm as it says in the second paragraph, by analogy with the cards , as in the first iteration of the array would be ordered because it is : array = [0 , 1, 1 , 2] . Wonder is necessary to continue the algorithm until through all the indices in the subarray as paragraph 6 states or stopped in the first iteration .

Accepted Answer

With selection sort, you have to go through all the iterations (the algorithm has no way of knowing if the array is sorted before it has done all the iterations) . However, you could try to optimize the algorithm by checking to see if the array was sorted.

To be able to skip future iterations once sorted, you would need to add a flag if an unsorted pair of neighbors was found, and then each pass, you would need to check, for each element whether each pair of neighbors was sorted. If not, the flag would be set to false. After each pass you could check the flag. If the flag was true, then you could skip the future iterations since the array was sorted. This optimization is often incorporated into bubble sort which compares neighbors anyhow ( bubble sort is O(n^2) but generally performs worse than the other O(n^2) sorting algorithms). The problem with adding this check to selection sort is it adds an additional comparison, which would make the algorithm slower for arrays which are not nearly sorted.

That being said, if you thought you were going to be sorting a lot of arrays that were nearly sorted, then you should just use insertion sort, which performs very well with nearly sorted arrays.

Hope this makes sense

Question 4

I fail to see why this doesn't work :(

for (var i = minIndex + 1; i === array.length - 1; i++) {
        
if (min(minValue, array[i]) < minValue) {
             
minIndex = i;
minValue = array[i];
}
}

Accepted Answer

There's a couple of issues: 
1)
Suppose we call:
`indexOfMinimum([2,9,1],0)`
The first time the for loop executes:
What is the value of `i` ?
What is the value of `array.length` ?
Is `i === array.length-1` true or false ? 
That should show the first problem.

2) 
- You shouldn't need to call the min function, in the condition of your if statement. You should be able to simplify that condition.

Good Luck

Question 5

In the challenge implement selection sort I had the code

`var swap = function(array, firstIndex, secondIndex) {
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
};

var indexOfMinimum = function(array, startIndex) {

var minValue = array[startIndex];
    var minIndex = startIndex;

for(var i = minIndex + 1; i < array.length; i++) {
        if(array[i] < minValue) {
            minIndex = i;
            minValue = array[i];
        }
    } 
    return minIndex;
};

var selectionSort = function(array) {
    var MinIndex;
    for(var StartingIndex;StartingIndex<array.length;StartingIndex++ ) {
        MinIndex = indexOfMinimum(array,StartingIndex);
        swap(array, StartingIndex, MinIndex);
    }
};

var array = [22, 11, 99, 88, 9, 7, 42];
selectionSort(array);
println("Array after sorting:  " + array);

Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);`

The Program.assertEqual said that my code was wrong. I don't know why the function selectionSort isn't working. Can you help me?

Accepted Answer

`StartingIndex` isn't initialized to any value, so it is `null` (which is an invalid input to the `indexOfMinimum` function).

As a side note, the general convention in JavaScript for variable names is camel case with the initial letter in lower case i.e. `startingIndex` instead of `StartingIndex`. It won't impact how your code works, but it will make it easier for others to read your code if you follow the convention.

Computer science theory

Course: Computer science theory > Unit 1

Selection sort pseudocode

Finding the index of the minimum element in a subarray

Want to join the conversation?