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

leonW
I ran this command after installing the sample application: $ cards add do something --owner Brian And got a file not found error: Fil...
New
patoncrispy
I’m new to Rust and am using this book to learn more as well as to feed my interest in game dev. I’ve just finished the flappy dragon exa...
New
jskubick
I’m running Android Studio “Arctic Fox” 2020.3.1 Patch 2, and I’m embarrassed to admit that I only made it to page 8 before running into ...
New
jskubick
I think I might have found a problem involving SwitchCompat, thumbTint, and trackTint. As entered, the SwitchCompat changes color to hol...
New
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
adamwoolhether
Is there any place where we can discuss the solutions to some of the exercises? I can figure most of them out, but am having trouble with...
New
taguniversalmachine
Hi, I am getting an error I cannot figure out on my test. I have what I think is the exact code from the book, other than I changed “us...
New
tkhobbes
After some hassle, I was able to finally run bin/setup, now I have started the rails server but I get this error message right when I vis...
New
dachristenson
@mfazio23 Android Studio will not accept anything I do when trying to use the Transformations class, as described on pp. 140-141. Googl...
New

Other popular topics Top

AstonJ
A thread that every forum needs! Simply post a link to a track on YouTube (or SoundCloud or Vimeo amongst others!) on a separate line an...
New
AstonJ
Curious to know which languages and frameworks you’re all thinking about learning next :upside_down_face: Perhaps if there’s enough peop...
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
If you are experiencing Rails console using 100% CPU on your dev machine, then updating your development and test gems might fix the issu...
New
PragmaticBookshelf
“A Mystical Experience” Hero’s Journey with Paolo Perrotta @nusco Ever wonder how authoring books compares to writing articles?...
New
PragmaticBookshelf
Build highly interactive applications without ever leaving Elixir, the way the experts do. Let LiveView take care of performance, scalabi...
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
First poster: joeb
The File System Access API with Origin Private File System. WebKit supports new API that makes it possible for web apps to create, open,...
New
husaindevelop
Inside our android webview app, we are trying to paste the copied content from another app eg (notes) using navigator.clipboard.readtext ...
New
CommunityNews
A Brief Review of the Minisforum V3 AMD Tablet. Update: I have created an awesome-minisforum-v3 GitHub repository to list information fo...
New

Sub Categories: