/*
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;
}
}
