From what I've read, even though their big Oh notation is the same, when bubble sorting and selection sorting an array, as the size of the array grows, selection sort should outperform bubble sort.
But in my code, bubble sort is consistently outperforming selection sort as the array gets bigger.
In the program, the user specifies the number of items to be in the array, and a number of times that an array of that many items should be created and sorted (to get a more accurate result).
This is my code:
import java.util.Scanner;
import java.util.Random;
public class SelectionSorting
{
public static int[] arr;
public static long runningSelectionTime, runningBubbleTime;
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
System.out.println("Please enter the number of the items in the array: ");
int i = in.nextInt();
System.out.println("Please enter the number of iterations: ");
int iters = in.nextInt();
arr = new int[i];
for (int x = 0; x < iters; x++)
{
for (int n = 0; n < i; n++)
{
arr[n] = randomness();
}
long startSelectionTime = System.nanoTime();
selectionSort(arr);
long endSelectionTime = System.nanoTime();
runningSelectionTime += endSelectionTime - startSelectionTime;
}
System.out.println("Selection Sort: ");
System.out.println("Total running time: " + runningSelectionTime + " and the average is " + runningSelectionTime/iters);
for (int x = 0; x < iters; x++)
{
for (int n = 0; n < i; n++)
{
arr[n] = randomness();
}
long startBubbleTime = System.nanoTime();
bubbleSort(arr);
long endBubbleTime = System.nanoTime();
runningBubbleTime += endBubbleTime - startBubbleTime;
}
System.out.println("Bubble Sort: ");
System.out.println("Total running time: " + runningBubbleTime + " and the average is " + runningBubbleTime/iters);
}
public static void selectionSort(int[] array)
{
for (int i = 0; i < array.length - 1; i++)
{
int iMin = i;
for (int j = i + 1; j < array.length; j++)
{
if (array[j] < array[iMin])
{
iMin = j;
}
}
if (iMin != i)
{
int temp = array[i];
array[i] = array[iMin];
array[iMin] = temp;
}
}
}
public static void bubbleSort(int[] arr)
{
int unsorted = arr.length;
while (unsorted != 0)
{
int lastSwap = 0;
for (int i = 1; i < unsorted; i++)
{
if (arr[i - 1] > arr[i])
{
swap(arr, i, i - 1);
lastSwap = i;
}
}
unsorted = lastSwap;
}
}
private static void swap(int[] arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static int randomness()
{
Random rand = new Random();
int random = rand.nextInt();
if (random < 0)
{
random = random * -1;
}
do {
random = random / 10;
} while (random > 100);
return random;
}
}
If you try putting in 500 and 1000, the running time of bubble sort will be shorter than that of selection sort.
Interestingly enough, if I get rid of the variable "iters," then the results are as expected. However, it would seem that iters should make the running time more accurate, not less.
Any ideas as to why that is? Did I do something wrong? Is it possible for bubble sort to outperform selection sort (consistently)?
(To prevent any confusion, I have seen the question Why is my Java based Bubble Sort Outperforming my Selection sort and my Insertion Sort?, but it does not address the same problem.)
