Problem
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] + " ");
}
}
}
Solution
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;
}
}
}
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.