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

jimmykiang
This test is broken right out of the box… — FAIL: TestAgent (7.82s) agent_test.go:77: Error Trace: agent_test.go:77 agent_test.go:...
New
jon
Some minor things in the paper edition that says “3 2020” on the title page verso, not mentioned in the book’s errata online: p. 186 But...
New
telemachus
Python Testing With Pytest - Chapter 2, warnings for “unregistered custom marks” While running the smoke tests in Chapter 2, I get these...
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
mikecargal
Title: Hands-on Rust: question about get_component (page 295) (feel free to respond. “You dug you’re own hole… good luck”) I have somet...
New
Charles
In general, the book isn’t yet updated for Phoenix version 1.6. On page 18 of the book, the authors indicate that an auto generated of ro...
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
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
Keton
When running the program in chapter 8, “Implementing Combat”, the printout Health before attack was never printed so I assumed something ...
New
dachristenson
I just bought this book to learn about Android development, and I’m already running into a major issue in Ch. 1, p. 20: “Update activity...
New

Other popular topics Top

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
PragmaticBookshelf
Design and develop sophisticated 2D games that are as much fun to make as they are to play. From particle effects and pathfinding to soci...
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
PragmaticBookshelf
Rust is an exciting new programming language combining the power of C with memory safety, fearless concurrency, and productivity boosters...
New
AstonJ
Thanks to @foxtrottwist’s and @Tomas’s posts in this thread: Poll: Which code editor do you use? I bought Onivim! :nerd_face: https://on...
New
dimitarvp
Small essay with thoughts on macOS vs. Linux: I know @Exadra37 is just waiting around the corner to scream at me “I TOLD YOU SO!!!” but I...
New
DevotionGeo
The V Programming Language Simple language for building maintainable programs V is already mentioned couple of times in the forum, but I...
New
PragmaticBookshelf
Author Spotlight Jamis Buck @jamis This month, we have the pleasure of spotlighting author Jamis Buck, who has written Mazes for Prog...
New
Help
I am trying to crate a game for the Nintendo switch, I wanted to use Java as I am comfortable with that programming language. Can you use...
New

Sub Categories: