Bubble Sort Outperforming Selection Sort?

Question

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.)

Answer 1

Your bubble sort is faster because it does not work.

      arr[i] = temp;

should be

      arr[i-1] = temp;

output for 10000 * 3

Selection Sort:
Total running time: 216077472 and the average is 72025824
Bubble Sort:
Total running time: 402583050 and the average is 134194350

output for 500 * 1000

Selection Sort:
Total running time: 123621068 and the average is 123621
Bubble Sort:
Total running time: 317450183 and the average is 317450

using using jdk 7