A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Are Selection Sort steps wrong? (page 71)

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.

Hi,

This is a really good catch! I think that for Selection Sort, the worst case scenario is still 4 swaps, but you’re right that an array in perfect descending order happens not to be the worst case scenario for Selection Sort.

An array like this: [5, 3, 1, 2, 4] - will still give you 4 swaps in Selection Sort.

I’ll have to clarify this in the next version. Thank you!

-Jay

1 Like