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

Pragmatic Bookshelf PragProg Customers
,
1

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.

1 Like