Shalvin Interests

Thursday, September 15, 2011

Insertion Sort in C#





using System;

public class InsertionSort
{
   private int[] data; 
   private static Random generator = new Random();

   public InsertionSort( int size )
   {
      data = new int[ size ]; 

      for ( int i = 0; i < size; i++ )
         data[ i ] = generator.Next( 10, 100 );
   } 

   public void Sort()
   {
      int insert;

      for ( int next = 1; next < data.Length; next++ )
      {
           insert = data[ next ]; 

           int moveItem = next; 

         // search for place to put current element
         while ( moveItem > 0 && data[ moveItem - 1 ] > insert )
         {
            // shift element right one slot
            data[ moveItem ] = data[ moveItem - 1 ];
            moveItem--;
         } 

         data[ moveItem ] = insert; // place inserted element
         PrintPass( next, moveItem ); 
      } 
   } 

   public void PrintPass( int pass, int index )
   {
      Console.Write( "after pass {0}: ", pass );

      for ( int i = 0; i < index; i++ )
         Console.Write( data[ i ] + "  " );

      Console.Write( data[ index ] + "* " ); // indicate swap

      for ( int i = index + 1; i < data.Length; i++ )
         Console.Write( data[ i ] + "  " );
     
      Console.Write( "\n              " ); 

      // indicate amount of array that is sorted
      for( int i = 0; i <= pass; i++ )
         Console.Write( "--  " );
      Console.WriteLine( "\n" ); 
   } 

   public override string ToString()
   {
      string temporary = "";

      foreach ( int element in data )
         temporary += element + "  ";
     
      temporary += "\n"; // add newline character
      return temporary;
   } 
} 


using System;

public class InsertionSortTest
{
   public static void Main( string[] args )
   {
      InsertionSort sortArray = new InsertionSort( 10 );
      
      Console.WriteLine( "Unsorted array:" );
      Console.WriteLine( sortArray ); 
      sortArray.Sort(); 

      Console.WriteLine( "Sorted array:" );
      Console.WriteLine( sortArray );
      Console.ReadLine();
   } 
} 

No comments:

Post a Comment