1

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 ( "" );
  }
}
3
Contributors
2
Replies
4
Views
12 Years
Discussion Span
Last Post by majestic0110
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.