So  ..our student , Jeff was trying to write an method that sorts an array of ints  , called nums , using a single loop. He wrote the code below:. Download code .   Here you can download a powerpoint with a step by step visual explanation.

So, was Jeff successful? When this code is run, will the method return a sorted array. In this case that would be  {20, 80, 90 100}   ?

 

 

And the Answer is ….

 

 

NO! Alas, young Jeffrey did not succeed

 

 

Now, can you figure out why this does not sort the actual array ?

 

It turns out that you cannot sort a list by just swapping consecutive elements.

 

nums[i] and nums[i+1]   are consecutive.

At least not in the way that this code is written-using a  single loop over the elements. The only time that two elements get swapped is when the two elements directly next to each other are compared .
So, in the first comparison when i =0 and i+1 = 1, the code correctly decides that  the first two elements are in the right spot..but , now we find ourselves at i =1 and we’re comparing the numbers ’20’ and ’90’ to decide what goes at index =1 (ie where the ’20’ is). The problem is…if we want the whole array to be sorted we need the  last element (80) to be in the spot where ’20’ currently is…and the only comparison we are making right now is between ’20’ and  ’90’.

To explore how sorting works and some of the formal sorting algorithms, check out our Sort Detective – which allows you to explore the properties of various popular sorting algorithms.

 

For a more detailed lesson, download the powerpoint here.