According to what I’ve read, even if their big Ah notation is the same when bubble sorting and selection sorting an array, selection sort should outperform bubble sort as the size of the array rises.
But, in my implementation, bubble sort consistently outperforms selection sort as the array grows larger.
The user specifies the number of items to be in the array and the number of times an array of that many items is to be produced and sorted throughout the program (to get a more accurate result).
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;
}
}
When you enter 500 and 1000, the running time of the bubble sort is less than that of the selection sort.
Surprisingly, when I remove the variable “items,” the results are as predicted. Yet, it appears that items should make the running time more accurate rather than less.
Do you have any suggestions why this is the case? Did I make a mistake? Is it possible for bubble sort to regularly beat selection sort?
I read this article and saw this post on stackoverflow about Java-based Bubble Sort Outperforming my Selection Sort and Insertion Sort? but it doesn’t address the same issue.