Best Case, O(n^2)

Worst Case, Ω(n^2)

Memory Complexity, O(1)

import java.util.Random;
import java.util.Arrays;

public class Select
{
    //select sort	
    public static void selectSort(int arr[])
    {
	int n = arr.length;
 
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n-1; i++)
        {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;
 
            // Swap the found minimum element with the first
            // element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    //generate an array with random elements
    public static int [] getArray(int size)
    {
	    int [] array = new int[size];
	    Random r = new Random();

	    for(int i = 0; i < size; i++)
		    array[i] = r.nextInt(100);

	    return array;
    }

    //display an array
    public static void displayArray(int arr[])
    {
	    for(int e : arr)
		    System.out.printf("%5d", e);
	    System.out.println();
    }

    public static void main(String args[])
    {
	    long start, end;
	    int [] array;
	    int [] array2;
	    int size = 100000;

	    //create two same arrays
	    array = getArray(size);
	    array2 = Arrays.copyOf(array, array.length);

	    //sort a huge array with select sort
	    start = System.currentTimeMillis();
	    selectSort(array);
	    end = System.currentTimeMillis();
	    System.out.printf("Bubble sort time: %10f%n", (end-start)/1000000.0);

	    //sort the array with build-in sort function in Arrays class
	    start = System.currentTimeMillis();
	    Arrays.sort(array2);
	    end = System.currentTimeMillis();
	    System.out.printf("Build-in sort time: %10f%n", (end-start)/1000000.0);

	    //validate select sort
	    if(Arrays.equals(array, array2))
		    System.out.println("Bubble sort is validated ...");
	    else
		    System.out.println("Bubble sort does not work correctly ...");
    }
}