Possible sub-optimal selection sort

Question

Why is this code "bad"? In all of the selection sort codes I am learning from, they do it much differently. I will learn the proper code from the book, but I would love to know why this particular code is bad.

public class Main {
 public static void main(String[] args) {
 int[] array = {8, 3, 5, 7, 9, 2, 4, 6, 8, 0};
 System.out.println("The sorted array is: ");
 displayArray(selectionSort(array));
 }
 public static int[] selectionSort(int[] list) {
 int[] result = list;
 for (int i = 0; i < result.length - 1; i++) {
 for (int j = i + 1; j < result.length; j++) {
 if (result[i] > result[j]) {
 int temp = result[i];
 result[i] = result[j];
 result[j] = temp;
 }
 }
 }
 return result;
 }
 public static void displayArray(int[] list) {
 for (int i = 0; i < list.length; i++) {
 if ((i + 1) % 5 == 0)
 System.out.println(list[i]);
 else
 System.out.print(list[i] + " ");
 }
 }
}

• FabZeros: My question refers to the selectionSort method, but I took the opportunity to post some more in case anything else is amiss.
• Jamal: What do you mean by "bad"? Does it not work properly?
• FabZeros: It's very different from the book.

Answer 1

Too many swaps

The "standard" selection sort finds the minimum element and swaps the first element with the minimum element once per loop. In total there should be N swaps. Your version of selection sort can swap up to (N^2)/2 times.

Unnecessary variable

I'm not sure why you use the variable result and return it. You can just operate on the array that is passed in (list) directly. When I first read your code I thought you were making a copy of the array, because you had this extraneous variable.

The "standard" selection sort

Here is an example of a "standard" selection sort:

public static void selectionSort(int[] list)
{
 int len = list.length;
 for (int i = 0; i < len - 1; i++) {
 int smallestIndex = i;
 int smallestValue = list[i];
 for (int j = i + 1; j < len; j++) {
 if (list[j] < smallestValue) {
 smallestIndex = j;
 smallestValue = list[j];
 }
 }
 if (smallestIndex != i) {
 list[smallestIndex] = list[i];
 list[i] = smallestValue;
 }
 }
}

• FabZeros: Thank you for your very concise answer! Exactly what I needed!
• FDinoff: Where is he making a copy?
• JS1: @FDinoff You're right. I just read "result" and saw that it was returned and assumed he was returning a copy. I'll edit the answer.

Answer 2

Sorting

This code:

for (int i = 0; i < result.length - 1; i++) {
 for (int j = i + 1; j < result.length; j++) {
 if (result[i] > result[j]) {
 int temp = result[i];
 result[i] = result[j];
 result[j] = temp;
 }
 }
}

Is not how Selection sort works. At first glance it looks like Bubble sort, but considering how it actually works, it looks more like a form of "ping-pong sort" (yes, I just made that up).

So, how does your current code work?

I added a little output whenever two elements were swapped and this was the results of the first swaps:

[8, 3, 5, 7, 9, 2, 4, 6, 8, 0] --> [3, 8, 5, 7, 9, 2, 4, 6, 8, 0] (flipped 0 and 1)
[3, 8, 5, 7, 9, 2, 4, 6, 8, 0] --> [2, 8, 5, 7, 9, 3, 4, 6, 8, 0] (flipped 0 and 5)
[2, 8, 5, 7, 9, 3, 4, 6, 8, 0] --> [0, 8, 5, 7, 9, 3, 4, 6, 8, 2] (flipped 0 and 9)
[0, 8, 5, 7, 9, 3, 4, 6, 8, 2] --> [0, 5, 8, 7, 9, 3, 4, 6, 8, 2] (flipped 1 and 2)
[0, 5, 8, 7, 9, 3, 4, 6, 8, 2] --> [0, 3, 8, 7, 9, 5, 4, 6, 8, 2] (flipped 1 and 5)
[0, 3, 8, 7, 9, 5, 4, 6, 8, 2] --> [0, 2, 8, 7, 9, 5, 4, 6, 8, 3] (flipped 1 and 9)
[0, 2, 8, 7, 9, 5, 4, 6, 8, 3] --> [0, 2, 7, 8, 9, 5, 4, 6, 8, 3] (flipped 2 and 3)

As you can see, whenever a new minimum value has been found, it swaps the current index value with that new minimum value. At the third flip for example, the 2 is moved to the end of the array, even though it should (and will, eventually) end up at index 1. Therefore, pretty much all elements will sooner or later be at the last index, so they are moved back and forth quite a bit, hence I am calling it "ping-pong sort".

Class Name

public class Main {

Would be better named as SelectionSort (or SomeOtherSort as it isn't real SelectionSort - yet).

Braces, and toString

Your displayArray method lacks some braces. It is recommended to always use braces. Even for one-liners.

You should also know, even though the methods don't work exactly the same, that there is a Arrays.toString method to convert any array to a good string representation.

• JS1: I thought it was a bubble sort too at first, but actually it isn't. It doesn't swap adjacent elements. It swaps the first element repeatedly with smaller elements to its right.
• Simon Forsberg: @JS1 You're right, it wasn't. Good observation. I edited a bit and showed how it actually works. I am giving it the name "ping-pong sort".