Insertion sort, Selection sort, Bubble sort, Shell sort, Quicksort, and Heapsot. All optimized and ready to be experimented with. This is the framework for a Java application that speed tests various sorting algorithms (because there's usually little need to write one's own in production programs). Several popular algorithms were left out because I didn't feel like implementing them. Included in this list are counting sorts, radix sorts, merge sorts, and the introsort. All are interesting, but I get bored quickly.

``````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 ( "" );
}
}``````

Thank you very much for this!

Very nice. Much better (and cleaner) than my version!