[computer science] c programming

import java.util.Random; public class MergeSort { private static final int MAX_TEST_SIZE = 1000; public static void main( String[] args ) { double[] data = new double[MAX_TEST_SIZE]; Random random = new Random( ); System.out.println( "Testing Merge Sort Implementation" ); for( int i = 0; i < data.length; i++ ) { // use as many as i entries for( int j = 0; j < i; j++ ) { // the equal item data[j] = i / 2; } sort( data, i ); if( !isSorted( data, i ) ) { System.out.println( "FAILED: Equal Items. Size=" + i ); } for( int j = 0; j < i; j++ ) { // items in ascending order data[j] = j - (i / 2); } sort( data, i ); if( !isSorted( data, i ) ) { System.out.println( "FAILED: Ascending Order. Size=" + i ); } for( int j = 0; j < i; j++ ) { // items in descending order data[j] = (i / 2) - j; } sort( data, i ); if( !isSorted( data, i ) ) { System.out.println( "FAILED: Descending Order. Size=" + i ); } for( int j = 0; j < i; j++ ) { // items in random order data[j] = random.nextDouble( ) - 0.5; } sort( data, i ); if( !isSorted( data, i ) ) { System.out.println( "FAILED: Random Order. Size=" + i ); } } System.out.println( "\n*** END OF PROCESSING ***\n" ); } public static boolean isSorted( double[] data, int length ) { boolean sorted = true; if( data != null && length > 0 ) { for( int i = 1; sorted && i < length; i++ ) { if( data[i - 1] > data[i] ) { sorted = false; } } } return sorted; } public static void sort( double[] data, int length ) { double[] auxiliary = new double[MAX_TEST_SIZE]; boolean dataInAux = false; if( data != null && length > 0 ) { dataInAux = mergeSort( data, auxiliary, 0, length ); if( dataInAux ) { // move data from auxiliary to data array for( int i = 0; i < length; ++i ) { data[i] = auxiliary[i]; } } } } //-------------------------------------------------- // mergeSort // PURPOSE: Perform merge sort using auxiliary buffer // INPUT PARAMETERS: // [data]<IN> Data to sort. It may contains sorted data after the function call (see return) // [auxiliary]<IN> Buffer array. It may contain sorted data after the function call (see return) // [beginIndex]<IN> Begin index of data to sort (inclusive) // [endIndex]<IN> End index of data to sort (exclusive) // OUTPUT PARAMETERS: // [boolean]<OUT> True, if sorted data is in 'auxiliary'; false, if sorted data is in 'data' // REMARKS: By using auxiliary, the function can improve its performance. However, the function // does not guarantee where the sorted data's stored after the process. Check return variable // to make sure which array contains the end result. // While auxiliary array can have different size from data array, as long as it is bigger, // it is generally good idea to have the same size. //-------------------------------------------------- public static boolean mergeSort( double[] data, double[] auxiliary, int beginIndex, int endIndex ) { boolean dataInAux = false; if( endIndex - beginIndex <= 1 ) { // base case, already sorted } else if( endIndex - beginIndex <= 2 ) { // base case, sort two items // In reality, it is faster to use insertion sort with small N (~1024??) // but we just stick to current implementation for now. if( data[beginIndex] > data[beginIndex + 1] ) { auxiliary[beginIndex + 1] = data[beginIndex]; auxiliary[beginIndex] = data[beginIndex + 1]; dataInAux = true; // data is now in auxiliary buffer } } else { // divide and conquer int auxIndex; // index on auxiliary array int idx1, idx2; // index on data array boolean fstInAux; // the first half's data is in auxiliary array boolean sndInAux; // the second half's data is in auxiliary array int middle = (endIndex - beginIndex) / 2 + beginIndex; fstInAux = mergeSort( data, auxiliary, beginIndex, middle ); sndInAux = mergeSort( data, auxiliary, middle, endIndex ); dataInAux = !sndInAux; // after merging process, data will be on other array if( sndInAux ) { // swap array pointers, because we conceptually copy from data to auxiliary double[] tmp = data; data = auxiliary; auxiliary = tmp; } if( fstInAux != sndInAux ) { // Remember that we swapped the pointer above. // Thus, second half's data is in array which is pointed by 'data' // and first half's data is currently in array which is pointed by 'auxiliary' for( idx1 = beginIndex; idx1 < middle; idx1++ ) { // copy first half's data, because it tends to have one less data to copy. data[idx1] = auxiliary[idx1]; // make sure all data to be merged are in the same place. } } auxIndex = beginIndex; // index on auxiliary buffer idx1 = beginIndex; // index on first half of the data idx2 = middle; // index on second half of the data while( idx1 < middle && idx2 < endIndex ) { // merge items in order if( data[idx1] < data[idx2] ) { auxiliary[auxIndex++] = data[idx1++]; } else { auxiliary[auxIndex++] = data[idx2++]; } } while( idx1 < middle ) { // we copy the rest of the first half's data after completing the second half's auxiliary[auxIndex++] = data[idx1++]; } while( idx2 < endIndex ) { // we copy the rest of the second half's data after completing the first half's auxiliary[auxIndex++] = data[idx2++]; } } return dataInAux; } }