Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Selection Sort
import java.util.Comparator;
public class Selection
{
private Selection() { }
public static void sort( Comparable[] a )
{
int n = a.length;
for ( int i = 0; i < n; i++ )
{
int min = i;
for ( int j = i + 1; j < n; j++ )
{
if ( less( a[ j ], a[ min ] ) ) min = j;
}
exch( a, i, min );
assert isSorted( a, 0, i );
}
assert isSorted( a );
}
public static void sort( Object[] a, Comparator comparator )
{
int n = a.length;
for ( int i = 0; i < n; i++ )
{
int min = i;
for ( int j = i + 1; j < n; j++ )
{
if ( less( comparator, a[ j ], a[ min ] ) ) min = j;
}
exch( a, i, min );
assert isSorted( a, comparator, 0, i );
}
assert isSorted( a, comparator );
}
private static boolean less( Comparable v, Comparable w )
{
return v.compareTo( w ) < 0;
}
private static boolean less( Comparator comparator, Object v, Object w )
{
return comparator.compare( v, w ) < 0;
}
private static void exch( Object[] a, int i, int j )
{
Object swap = a[ i ];
a[ i ] = a[ j ];
a[ j ] = swap;
}
private static boolean isSorted( Comparable[] a )
{
return isSorted( a, 0, a.length - 1 );
}
private static boolean isSorted( Comparable[] a, int lo, int hi )
{
for ( int i = lo + 1; i <= hi; i++ )
if ( less( a[ i ], a[ i - 1 ] ) ) return false;
return true;
}
private static boolean isSorted( Object[] a, Comparator comparator )
{
return isSorted( a, comparator, 0, a.length - 1 );
}
private static boolean isSorted( Object[] a, Comparator comparator, int lo, int hi )
{
for ( int i = lo + 1; i <= hi; i++ )
if ( less( comparator, a[ i ], a[ i - 1 ] ) ) return false;
return true;
}
private static void show( Comparable[] a )
{
for ( int i = 0; i < a.length; i++ )
{
StdOut.println( a[ i ] );
}
}
public static void main( String[] args )
{
String[] a = StdIn.readAllStrings();
Selection.sort( a );
show( a );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment