1. SelectionSort

책상 위 컴퓨터/Data Structure & Algorithm 2008.05.06 08:39 Posted by 잡학 저장소 잡학저장소

/*
SelectionSort : sort contiguous list by the selection sort method.
Pre : The contiguous list list has been created. Each entry of list contains a key.
Post : The entries of list have been rearranged so that the keys in all the entries are sorted into nondecreasing order.
Uses : MaxKey, Swap
*/

void SelectionSort( List * list ){
   Position current; /* position of place being correctly filled */
   Position max; /* position of largest remaining key */
   for ( current = list -> count - 1; current > 0; current-- ){
      max = MaxKey ( 0, current, list );
      Swap ( max, current, list );
   }
}


/*
MaxKey : find the position of the largest key in the sublist.
Pre : The contiguous list list has been created. low and high are valid positions in list.
Post : The position of the entry between low and high with the largest key is returned
*/

Position MaxKey( Position low, Position high, List * list ){
   Position largest; /* position of largest key so far */
   Position current; /* index for the contigous list */
   largest = low;
   for( current = low + 1; current <= high; current++ )
      if( LT( list->entry[ largest ].key, list->entry[ current ].key ) )
         largest = current; 

   return largest;
}


/*
Swap : swap two entries in the contiguos list.
Pre : The contiguos list list has been created. low and high are valied positions in list.
Post : The entry at position low is swapped with the entry at position high
*/

void Swap( Position low, Position high, List * list ){
   ListEntry temp = list->entry[ low ];
   list->entry[ low ] = list->entry[ high ];
   list->entry[ high ] = temp;
}


/* 발췌 ---------------- Data Structures And Program Design in C */

public class Test {
   public static void main(String [] args){
      int [] array = { 7, 2, 3, 1, 5, 6 };
      SelectionSort selectionSort = new SelectionSort(array);
      selectionSort.runSort();
      selectionSort.print();
   }
}

class SelectionSort{
 
   int [] array;
 
   public SelectionSort(int [] array){
      this.array = array;
   }
 
   public void runSort(){
      int current;
      int max;
      for( current = array.length-1; current > 0 ; current-- ){
         max = this.getMaxKey( 0, current , array);
         runSwap( max, current, array );
      }
   }
 
   public int print(){
      int length = this.array.length;
      for( int count = 0; count < length; count++ )
         System.out.println(array[count]);
      return length;
   }
 
   private int getMaxKey( int low, int high, int [] array ){
 
      int largest;
      int current;
      largest = low;
 
      for( current = low+1 ; current <= high; current++ ){
        if( array[ largest ] <= array[ current ] ){
           largest = current;
        }
     }
 
    return largest;
 }
 
   private void runSwap( int low, int high, int [] array ){
      int temp = array[ high ];
      array[ high ] = array[ low ];
      array[ low ] = temp;
   }
}