frasette

frasette

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.

Marked As Solved

jaywengrow

jaywengrow

Author of A Common-Sense Guide to Data Structures and Algorithms

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

Where Next?

Popular Pragmatic Bookshelf topics Top

abtin
page 20: … protoc command… I had to additionally run the following go get commands in order to be able to compile protobuf code using go...
New
GilWright
Working through the steps (checking that the Info,plist matches exactly), run the demo game and what appears is grey but does not fill th...
New
simonpeter
When I try the command to create a pair of migration files I get an error. user=&gt; (create-migration "guestbook") Execution error (Ill...
New
swlaschin
The book has the same “Problem space/Solution space” diagram on page 18 as is on page 17. The correct Problem/Solution space diagrams ar...
New
brian-m-ops
#book-python-testing-with-pytest-second-edition Hi. Thanks for writing the book. I am just learning so this might just of been an issue ...
New
digitalbias
Title: Build a Weather Station with Elixir and Nerves: Problem connecting to Postgres with Grafana on (page 64) If you follow the defau...
New
brunogirin
When trying to run tox in parallel as explained on page 151, I got the following error: tox: error: argument -p/–parallel: expected one...
New
oaklandgit
Hi, I completed chapter 6 but am getting the following error when running: thread 'main' panicked at 'Failed to load texture: IoError(O...
New
a.zampa
@mfazio23 I’m following the indications of the book and arriver ad chapter 10, but the app cannot be compiled due to an error in the Bas...
New
bjnord
Hello @herbert ! Trying to get the very first “Hello, Bracket Terminal!" example to run (p. 53). I develop on an Amazon EC2 instance runn...
New

Other popular topics Top

New
PragmaticBookshelf
Free and open source software is the default choice for the technologies that run our world, and it’s built and maintained by people like...
New
AstonJ
What chair do you have while working… and why? Is there a ‘best’ type of chair or working position for developers?
New
dasdom
No chair. I have a standing desk. This post was split into a dedicated thread from our thread about chairs :slight_smile:
New
AstonJ
We have a thread about the keyboards we have, but what about nice keyboards we come across that we want? If you have seen any that look n...
New
AstonJ
This looks like a stunning keycap set :orange_heart: A LEGENDARY KEYBOARD LIVES ON When you bought an Apple Macintosh computer in the e...
New
rustkas
Intensively researching Erlang books and additional resources on it, I have found that the topic of using Regular Expressions is either c...
New
AstonJ
We’ve talked about his book briefly here but it is quickly becoming obsolete - so he’s decided to create a series of 7 podcasts, the firs...
New
AstonJ
Was just curious to see if any were around, found this one: I got 51/100: Not sure if it was meant to buy I am sure at times the b...
New
AstonJ
This is a very quick guide, you just need to: Download LM Studio: https://lmstudio.ai/ Click on search Type DeepSeek, then select the o...
New

Sub Categories: