sort3.txt

bubble,insertion, selection排序

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <math.h>
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
// constants, enums, and structs
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
enum eSortType { BUBBLESORT, SELECTIONSORT, INSERTIONSORT };


    struct tSortResults {
    	int nIndexIncrements;
    	int nOtherManuevers;
    	int nAssignments;
    	int nComparisons;
    	int nSwaps;
};
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
// function prototypes
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
tSortResults *bubbleSort(int Array[], const int Size );
tSortResults *selectionSort(int Array[], const int Size );
tSortResults *insertionSort(int nArray[], const int nSize);
int *returnRandomArray(int nSize);
void printArray(int Array[], const int nSize);
void excecuteSort(eSortType eType);
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
// application entry point, no command l
//     ine args
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////


    void main(void){
    	excecuteSort(BUBBLESORT);
    	excecuteSort(SELECTIONSORT);
    	excecuteSort(INSERTIONSORT);
}
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
// function definitions
////////////////////////////////////////
//     ////////////////////////////////////////
/////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////


    tSortResults *bubbleSort( int Array[], const int Size ){
    ////////////////////////////////////////
    //     ////////////////////////////////////////
    /////////
    // sort the given array via the bubble s
    //     ort algorithm
    int i, j, nTmp;
    	tSortResults *pResults = new tSortResults;
    	// where is the with statement when u need one? 
    	pResults->nAssignments = 0;
    	pResults->nComparisons = 0;
    	pResults->nIndexIncrements = 0;
    	pResults->nOtherManuevers = 0;
    	pResults->nSwaps = 0;
    	// loop thru the array


        for( i = 0; i < Size - 1; ++i ){
        		
        		pResults->nIndexIncrements ++;
        		// keep going, staying 1 back from the end


            		for( j = i + 1; j > 0; --j ){
            			
            			pResults->nIndexIncrements ++;
            			pResults->nComparisons ++;
            			// if the first is bigger, then swap em'


                			if( Array[j] < Array[j - 1] ){
                				// do the swap
                				pResults->nSwaps ++;
                				pResults->nAssignments ++;
                				
                				nTmp = Array[j];
                				pResults->nAssignments ++;
                				Array[j] = Array[j - 1];
                				pResults->nAssignments ++;
                				Array[j - 1] = nTmp;
                			}
                		}
                	}
                	// pass back the results 
                	return pResults;
            }


                tSortResults *selectionSort( int Array[], const int Size ){
                ////////////////////////////////////////
                //     ////////////////////////////////////////
                /////////
                // sort the given array via the selectio
                //     n sort algorithm
                int i, j, nSmallest, nTmp;
                	
                	tSortResults *pResults = new tSortResults;
                	// where is the with statement when u need one? 
                	pResults->nAssignments = 0;
                	pResults->nComparisons = 0;
                	pResults->nIndexIncrements = 0;
                	pResults->nOtherManuevers = 0;
                	pResults->nSwaps = 0;
                	// loop thru the array


                    for( i = 0; i < Size; i++ ){
                    		
                    		pResults->nIndexIncrements ++;
                    		// assign a value to the smallest 
                    nSmallest = i;
                    		
                    		pResults->nAssignments ++;
                    		// keey going in the array


                        for( j = i; j < Size; j++ ){
                        			
                        			pResults->nIndexIncrements ++;
                        			
                        			pResults->nComparisons ++;
                        			// check the rest of the array, if something is smaller, then swap em'


                            if( Array[nSmallest] > Array[j] ){
                            				
                            				pResults->nAssignments ++;
                            				nSmallest = j;
                            					
                            			}
                        } 
                        		
                        		// do the swap
                        		pResults->nSwaps ++;
                        		pResults->nAssignments ++;
                        nTmp = Array[i];
                        		pResults->nAssignments ++;
                        Array[i] = Array[nSmallest];
                        		pResults->nAssignments ++;
                        Array[nSmallest] = nTmp;
                    }
                    	// pass back the results 
                    	return pResults;
                }


                    tSortResults *insertionSort(int nArray[], const int nSize){
                    ////////////////////////////////////////
                    //     ////////////////////////////////////////
                    /////////
                    // sort the array via the insertion sort
                    //     algorithm
                    	
                    	tSortResults *pResults = new tSortResults;
                    	// where is the with statement when u need one? 
                    	pResults->nAssignments = 0;
                    	pResults->nComparisons = 0;
                    	pResults->nIndexIncrements = 0;
                    	pResults->nOtherManuevers = 0;
                    	pResults->nSwaps = 0;
                    	
                    	// loop thru the array


                        	for(int i = 0; i < nSize; i++ ){
                        		pResults->nIndexIncrements ++; 
                        		pResults->nAssignments ++; 
                        		
                        		// snag the current value
                        		int nTmp = nArray[i];
                        		
                        		pResults->nAssignments ++; 
                        		
                        		// start 1 behind the current
                        		int j = i - 1;
                        		
                        		pResults->nComparisons ++;
                        		
                        		// and head back to the start, checking each as we go by
                        		// if the previous value is larger, then swap em'


                            		while (nArray[j] > nTmp){
                            			
                            			pResults->nComparisons ++;
                            			pResults->nAssignments ++;
                            			
                            			// do the swap
                            			pResults->nSwaps ++;
                            			nArray[j + 1] = nArray[j];
                            			
                            			pResults->nAssignments ++; 
                            			
                            			j = j - 1;
                            		}
                            		
                            		pResults->nAssignments ++;
                            		
                            		// move forward once all previous are sorted 
                            		nArray[j+1] = nTmp;
                            	}
                            	
                            	// pass back the results 
                            	return pResults;
                        }


                            int *returnRandomArray(int nSize){
                            ////////////////////////////////////////
                            //     ////////////////////////////////////////
                            /////////
                            // snag a random array of nSize elements
                            //     , flip back to caller
                            	
                            	int *nArray = new int[nSize];
                            


                                	for( int i = 0; i < nSize; i++ ){
                                		nArray[i] = rand() % 100;
                                	}
                                	return nArray;
                            }


                                void printArray(int Array[], const int nSize){
                                ////////////////////////////////////////
                                //     ////////////////////////////////////////
                                /////////
                                // display the given array (ie x,x,x,x)
                                	
                                	// run thru and display


                                    	for( int i = 0; i < nSize; i++ ){
                                    		
                                    		if (((i % 10) == 0) && i ) printf("\n");
                                    		// watch for the end, don't step past with the comma


                                        		if (!((i + 1) < nSize)){
                                        			printf("%i",Array[i]);
                                        		}


                                            		else{
                                            			printf("%i,", Array[i] );
                                            		}
                                            	}
                                        }


                                            void excecuteSort(eSortType eType){
                                            ////////////////////////////////////////
                                            //     ////////////////////////////////////////
                                            /////////
                                            // test the selected algorithm
                                            	int i, *pArray;
                                            	
                                            	tSortResults *pResults;
                                            	
                                            	srand((unsigned)time(NULL));


                                                	for ( i = 10; i <= 50; i = i + 10){
                                                		pArray = returnRandomArray(i);
                                                		printf("[ Random Array ] \n[ ");
                                                		printArray(pArray, i);
                                                		printf(" ]\n\n");
                                                		


                                                    		switch (eType){
                                                    			case BUBBLESORT:
                                                    				pResults = bubbleSort(pArray, i);
                                                    				printf("[ Bubble Sorted Array ] \n[ ");
                                                    				break;
                                                    			case SELECTIONSORT:
                                                    				pResults = selectionSort(pArray, i);
                                                    				printf("[ Selection Sorted Array ] \n[ ");
                                                    				break;
                                                    			case INSERTIONSORT:
                                                    				pResults = insertionSort(pArray, i);
                                                    				printf("[ Insertion Sorted Array ] \n[ ");
                                                    				break;
                                                    		}
                                                    		printArray(pArray, i);


                                                        		if (pResults){
                                                        			printf(" ]\n\nIndexIncrements = %d\n",pResults->nIndexIncrements);
                                                        			printf("Comparisons = %d\n", pResults->nComparisons );
                                                        			printf("Assignments = %d\n", pResults->nAssignments );
                                                        			printf("Swaps = %d\n", pResults->nSwaps );
                                                        			printf("OtherManuevers = %d\n\n", pResults->nOtherManuevers );
                                                        		}
                                                        		
                                                        	}
                                                    }