1

```
package scratchpad;
import java.math.*;
class SortInsertion {
// Insertion sort
public static <T extends Comparable>
void insertion_sort ( T[] list, int size )
{
for ( int i = 1; i < size; i++ ) {
T save = list[i];
int j = i;
while ( j >= 1 && save.compareTo ( list[j - 1] ) < 0 ) {
list[j] = list[j - 1];
--j;
}
list[j] = save;
}
}
// Shell sort
public static <T extends Comparable>
void shell_sort ( T[] list, int size )
{
int h = 1;
while ( h <= size / 9 ) {
h = 3 * h + 1;
}
while ( h > 0 ) {
for ( int i = h; i < size; i++ ) {
T save = list[i];
int j = i;
while ( j >= h && save.compareTo ( list[j - h] ) < 0 ) {
list[j] = list[j - h];
j -= h;
}
list[j] = save;
}
h /= 3;
}
}
}
class SortExchange {
// Bubble sort
public static <T extends Comparable>
void bubble_sort ( T[] list, int size )
{
int bound = size - 1;
while ( bound > 0 ) {
int new_bound = 0;
for ( int i = 0; i < bound; i++ ) {
if ( list[i].compareTo ( list[i + 1] ) > 0 ) {
T save = list[i];
list[i] = list[i + 1];
list[i + 1] = save;
new_bound = i;
}
}
bound = new_bound;
}
}
// Quicksort
private static <T extends Comparable>
void quicksort ( T[] list, int l, int r )
{
int[] stack = new int[50];
int m, top = 0;
T pivot;
while ( true ) {
while ( r > l + 10 ) {
// Median of three partition
m = ( l + r ) / 2;
if ( list[l].compareTo ( list[m] ) > 0 ) {
T save = list[l]; list[l] = list[m]; list[m] = save;
}
if ( list[l].compareTo ( list[r] ) > 0 ) {
T save = list[l]; list[l] = list[r]; list[r] = save;
}
if ( list[m].compareTo ( list[r] ) > 0 ) {
T save = list[m]; list[m] = list[r]; list[r] = save;
}
if ( r - l <= 2 ) {
break;
}
pivot = list[m];
list[m] = list[r - 1];
list[r - 1] = pivot;
int i = l;
int j = r - 1;
while ( true ) {
while ( list[++i].compareTo ( pivot ) < 0 ) {
// No body
}
while ( list[--j].compareTo ( pivot ) > 0 ) {
// No body
}
if ( j < i ) {
break;
}
T save = list[i];
list[i] = list[j];
list[j] = save;
}
pivot = list[i];
list[i] = list[r - 1];
list[r - 1] = pivot;
// Simulated recursive calls
if ( j - l > r - i ) {
stack[top++] = l;
stack[top++] = j;
l = i + 1;
}
else {
stack[top++] = i + 1;
stack[top++] = r;
r = j;
}
}
if ( top == 0 ) {
break;
}
r = stack[--top];
l = stack[--top];
}
}
public static <T extends Comparable>
void quicksort ( T[] list, int size )
{
quicksort ( list, 0, size - 1 );
SortInsertion.insertion_sort ( list, size );
}
}
class SortSelection {
// Selection sort
public static <T extends Comparable>
void selection_sort ( T[] list, int size )
{
for ( int i = 0; i < size - 1; i++ ) {
int min = i;
for ( int j = i + 1; j < size; j++ ) {
if ( list[j].compareTo ( list[min] ) < 0 ) {
min = j;
}
}
if ( min != i ) {
T save = list[i];
list[i] = list[min];
list[min] = save;
}
}
}
// Heapsort
private static <T extends Comparable>
void push_down ( T[] list, int l, int r )
{
int i, j;
for ( i = l; ( j = i * 2 + 1 ) <= r; i = j ) {
if ( j + 1 <= r && list[j + 1].compareTo ( list[j] ) > 0 ) {
++j;
}
T save = list[i];
list[i] = list[j];
list[j] = save;
}
while ( true ) {
j = ( i - 1 ) / 2;
if ( j < l || j == i || list[j].compareTo ( list[i] ) > 0 ) {
break;
}
T save = list[i];
list[i] = list[j];
list[j] = save;
i = j;
}
}
public static <T extends Comparable>
void heapsort ( T[] list, int size )
{
if ( size-- < 2 ) {
return;
}
int i;
for ( i = ( size - 1 ) / 2; i >= 0; i-- ) {
push_down ( list, i, size );
}
while ( size > 0 ) {
T save = list[size];
list[size] = list[0];
list[0] = save;
push_down ( list, 0, --size );
}
}
}
public class Main {
public static void main ( String[] args )
{
Integer[] a = new Integer[20];
for ( int i = 0; i < 20; i++ ) {
a[i] = (int)( Math.random() * 100 );
}
System.out.println ( "Before: " );
for ( int i : a ) {
System.out.print ( i + " " );
}
System.out.println ( "" );
// Insert your sorting method of choice here
System.out.println ( "After: " );
for ( int i : a ) {
System.out.print ( i + " " );
}
System.out.println ( "" );
}
}
```