Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Quick Sort
public class Quick
{
private Quick() { }
public static void sort( Comparable[] a )
{
StdRandom.shuffle( a );
sort( a, 0, a.length - 1 );
assert isSorted( a );
}
private static void sort( Comparable[] a, int lo, int hi )
{
if ( hi <= lo ) return;
int j = partition( a, lo, hi );
sort( a, lo, j - 1 );
sort( a, j + 1, hi );
assert isSorted( a, lo, hi );
}
private static int partition( Comparable[] a, int lo, int hi )
{
int i = lo;
int j = hi + 1;
Comparable v = a[ lo ];
while ( true )
{
while ( less( a[ ++i ], v ) )
{
if ( i == hi ) break;
}
while ( less( v, a[ --j ] ) )
{
if ( j == lo ) break;
}
if ( i >= j ) break;
exch( a, i, j );
}
exch( a, lo, j );
return j;
}
public static Comparable select( Comparable[] a, int k )
{
if ( k < 0 || k >= a.length )
{
throw new IllegalArgumentException( "index is not between 0 and " + a.length + ": " + k );
}
StdRandom.shuffle( a );
int lo = 0, hi = a.length - 1;
while ( hi > lo )
{
int i = partition( a, lo, hi );
if ( i > k ) hi = i - 1;
else if ( i < k ) lo = i + 1;
else return a[ i ];
}
return a[ lo ];
}
private static boolean less( Comparable v, Comparable w )
{
if ( v == w ) return false;
return v.compareTo( 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 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();
Quick.sort( a );
show( a );
assert isSorted( a );
StdRandom.shuffle( a );
StdOut.println();
for ( int i = 0; i < a.length; i++ )
{
String ith = ( String ) Quick.select( a, i );
StdOut.println( ith );
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment