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

johnp
Running the examples in chapter 5 c under pytest 5.4.1 causes an AttributeError: ‘module’ object has no attribute ‘config’. In particula...
New
Mmm
Hi, build fails on: bracket-lib = “~0.8.1” when running on Mac Mini M1 Rust version 1.5.0: Compiling winit v0.22.2 error[E0308]: mi...
New
JohnS
I can’t setup the Rails source code. This happens in a working directory containing multiple (postgres) Rails apps. With: ruby-3.0.0 s...
New
New
brunogirin
When I run the coverage example to report on missing lines, I get: pytest --cov=cards --report=term-missing ch7 ERROR: usage: pytest [op...
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
s2k
Hi all, currently I wonder how the Tailwind colours work (or don’t work). For example, in app/views/layouts/application.html.erb I have...
New
kolossal
Hi, I need some help, I’m new to rust and was learning through your book. but I got stuck at the last stage of distribution. Whenever I t...
New
Henrai
Hi, I’m working on the Chapter 8 of the book. After I add add the point_offset, I’m still able to see acne: In the image above, I re...
New
New

Other popular topics Top

AstonJ
If it’s a mechanical keyboard, which switches do you have? Would you recommend it? Why? What will your next keyboard be? Pics always w...
New
PragmaticBookshelf
Write Elixir tests that you can be proud of. Dive into Elixir’s test philosophy and gain mastery over the terminology and concepts that u...
New
PragmaticBookshelf
From finance to artificial intelligence, genetic algorithms are a powerful tool with a wide array of applications. But you don't need an ...
New
New
PragmaticBookshelf
Create efficient, elegant software tests in pytest, Python's most powerful testing framework. Brian Okken @brianokken Edited by Kat...
New
New
AstonJ
If you want a quick and easy way to block any website on your Mac using Little Snitch simply… File &gt; New Rule: And select Deny, O...
New
New
hilfordjames
There appears to have been an update that has changed the terminology for what has previously been known as the Taskbar Overflow - this h...
New
AstonJ
If you’re getting errors like this: psql: error: connection to server on socket “/tmp/.s.PGSQL.5432” failed: No such file or directory ...
New

Sub Categories: