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
iPaul
page 37 ANTLRInputStream input = new ANTLRInputStream(is); as of ANTLR 4 .8 should be: CharStream stream = CharStreams.fromStream(i...
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
ianwillie
Hello Brian, I have some problems with running the code in your book. I like the style of the book very much and I have learnt a lot as...
New
jesse050717
Title: Web Development with Clojure, Third Edition, pg 116 Hi - I just started chapter 5 and I am stuck on page 116 while trying to star...
New
jdufour
Hello! On page xix of the preface, it says there is a community forum "… for help if your’re stuck on one of the exercises in this book… ...
New
jgchristopher
“The ProductLive.Index template calls a helper function, live_component/3, that in turn calls on the modal component. ” Excerpt From: Br...
New
New
dsmith42
Hey there, I’m enjoying this book and have learned a few things alredayd. However, in Chapter 4 I believe we are meant to see the “&gt;...
New
rainforest
Hi, I’ve got a question about the implementation of PubSub when using a Phoenix.Socket.Transport behaviour rather than channels. Before ...
New

Other popular topics Top

PragmaticBookshelf
Take your Go skills to the next level by learning how to design, develop, and deploy a distributed service. Start from the bare essential...
New
PragmaticBookshelf
Brace yourself for a fun challenge: build a photorealistic 3D renderer from scratch! In just a couple of weeks, build a ray tracer that r...
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
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
PragmaticBookshelf
Rust is an exciting new programming language combining the power of C with memory safety, fearless concurrency, and productivity boosters...
New
PragmaticBookshelf
Tailwind CSS is an exciting new CSS framework that allows you to design your site by composing simple utility classes to create complex e...
New
Margaret
Hello everyone! This thread is to tell you about what authors from The Pragmatic Bookshelf are writing on Medium.
1147 29994 760
New
PragmaticBookshelf
Build efficient applications that exploit the unique benefits of a pure functional language, learning from an engineer who uses Haskell t...
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
New

Sub Categories: