Hi @jaywengrow,
I think the table of Selection Sort shows wrong Max number of steps.
For example, for N = 5 we sould have:
- Comparsions: 10 + Swaps: 2
and not:
- Comparsions: 10 + Swaps: 4
In the following code, edit size
variable to the number of element you want (5,10,20,40,80), run it to print comparsions and steps, and their sum, for a worst case scenario with a descending order array:
fiddle url: JsFiddle
function selectionSort(array) {
let comparsions = 0;
let swaps = 0;
for(let i = 0; i < array.length - 1; i++) {
let lowestNumberIndex = i;
for(let j = i + 1; j < array.length; j++) {
if(array[j] < array[lowestNumberIndex]) {
lowestNumberIndex = j;
}
comparsions++;
}
if(lowestNumberIndex != i) {
swaps++;
let temp = array[i];
array[i] = array[lowestNumberIndex];
array[lowestNumberIndex] = temp;
}
}
let steps = "Comparsions: " + comparsions + " Swaps: " + swaps;
console.log(steps);
return array;
}
// code to create a sample of array size = 5,10,20,40,80
let size = 80;
let counter = size;
let sample = new Array(size);
for (i = 0; i < size; i++) {
sample[i] = counter;
counter--;
}
console.log(selectionSort(sample))
What do you think? Thanks.