bubbleSort.c

/*--------------------------------------------------------------------------* *---- ----* *---- bubbleSort.c ----* *---- ----* *---- This file defines a function for sorting integers with the ----* *---- bubble-sort algorithm. ----* *---- ----* *---- ---- ---- ---- ---- ---- ---- ---- ---- ----* *---- ----* *---- Version 1.0 2016 April 1 Joseph Phillips ----* *---- ----* *--------------------------------------------------------------------------*/ #include "sortHeader.h" // PURPOSE: To sort the 'arrayLen' integers in array 'array[]' in ascending // order according to the bubble-sort algorithm. No return value. void bubbleSort (int arrayLen, int* array ) { // I. Application validity check: // II. Sort 'array[]': int haveExchanged; //int arrayLenMinusOne = arrayLen-1; // II.A. Each iteration redoes the inner loop while the inner loop // reported that it exchanged at least one adjacent pair: do { // II.A.1. Note that have not exchanged any pairs yet: haveExchanged = 0; // II.A.2. Go thru all 'array[]' and exchange any pairs that are // improperly ordered: int index; for (index = 0; index < arrayLen-1; index++) if (array[index] > array[index+1]) { exchange(array,index,index+1); haveExchanged = 1; } } while (haveExchanged); // III. Finished: } 

quickSort.c

/*--------------------------------------------------------------------------* *---- ----* *---- quickSort.c ----* *---- ----* *---- This file defines a function for sorting integers with the ----* *---- quick-sort algorithm. ----* *---- ----* *---- ---- ---- ---- ---- ---- ---- ---- ---- ----* *---- ----* *---- Version 1.0 2016 April 1 Joseph Phillips ----* *---- ----* *--------------------------------------------------------------------------*/ #include #include #include "sortHeader.h" // PURPOSE: To return the index of a pivot value about which to partition the // values between indices 'loIndex' and 'hiIndex'. in array 'array[]'. int quickSort_choosePivot (const int* array, int loIndex, int hiIndex ) { // I. Application valdity check: // II. Choose pivot value: // II.A. Compute index in the middle between 'loIndex' and 'hiIndex': int midIndex = (loIndex + hiIndex) / 2; // II.B. Return pivot index: if (array[loIndex] < array[hiIndex]) { if (array[midIndex] < array[loIndex]) return(loIndex); return( (array[midIndex] > array[hiIndex]) ? hiIndex : midIndex ); } else { if (array[midIndex] < array[hiIndex]) return(hiIndex); return( (array[midIndex] > array[loIndex]) ? loIndex : midIndex ); } } // PURPOSE: To partition the values between 'loIndex' and 'hiIndex' in array // 'array[]' such that all the values below a "pivot" value are moved to // between 'loIndex' and a "store index". Returns this "store index". int quickSort_partition (int* array, int loIndex, int hiIndex ) { int pivotIndex = quickSort_choosePivot(array,loIndex,hiIndex); int pivotValue = array[pivotIndex]; exchange(array,pivotIndex,hiIndex); int i; int storeIndex = loIndex; for (i = loIndex; i < hiIndex; i++) if (array[i] < pivotValue) { exchange(array,i,storeIndex); storeIndex++; } exchange(array,storeIndex,hiIndex); return(storeIndex); } // PURPOSE: To recursively sort the portion of array 'array[]' between // 'loIndex' and 'hiIndex' inclusive. No parameters. No return value. void quickSort_recursive (int* array, int loIndex, int hiIndex ) { // I. Application validity check: // II. Sort according to how many elements there are to sort: switch (hiIndex - loIndex) { case 0 : // II.A. One element: already sorted break; case 1 : // II.B. Two elements: compare them and exchange them if necessary: if (array[loIndex] > array[hiIndex]) exchange(array,loIndex,hiIndex); break; case 2 : // II.C. Three elements: place them in the proper order: { int midIndex = loIndex + 1; int loVal = array[loIndex]; int midVal = array[midIndex]; int hiVal = array[hiIndex]; int shouldExchLoAndHi = (loVal > hiVal); int shouldExchLoAndMid = (loVal > midVal); int shouldExchMidAndHi = (midVal > hiVal); if (shouldExchLoAndHi) { if (shouldExchLoAndMid) { if (shouldExchMidAndHi) { // 3,2,1 -> 1,2,3: exchange(array,loIndex,hiIndex); } else { // 3,1,2 -> 1,2,3: exchange(array,loIndex,hiIndex); exchange(array,loIndex,midIndex); } } else { if (shouldExchMidAndHi) { // 2,3,1 -> 1,2,3 exchange(array,hiIndex,midIndex); exchange(array,loIndex,midIndex); } else { fprintf(stderr, "BUG! Non-sensical quickSort_recursive() condition 0 " ); exit(EXIT_FAILURE); } } } else { if (shouldExchLoAndMid) { if (shouldExchMidAndHi) { fprintf(stderr, "BUG! Non-sensical quickSort_recursive() condition 1 " ); exit(EXIT_FAILURE); } else { // 2,1,3 -> 1,2,3: exchange(array,loIndex,midIndex); } } else { if (shouldExchMidAndHi) { // 1,3,2, -> 1,2,3: exchange(array,midIndex,hiIndex); } else { // 1,2,3 -> 1,2,3: // Already sorted } } } } break; default : // II.C. Four or more elements: partition array around pivot value: { int partIndex = quickSort_partition(array,loIndex,hiIndex); if (loIndex < partIndex) quickSort_recursive(array,loIndex,partIndex-1); quickSort_recursive(array,partIndex+1,hiIndex); } break; } // III. Finished: } // PURPOSE: To sort the 'arrayLen' integers in array 'array[]' in ascending // order according to the bubble-sort algorithm. No return value. void quickSort (int arrayLen, int* array ) { // I. Application validity check: // II. Sort all of 'array[]': quickSort_recursive(array,0,arrayLen-1); // III. Finished: } 

sortProg.c

/*--------------------------------------------------------------------------* *---- ----* *---- sortProg.c ----* *---- ----* *---- This file defines high-level and low-level functions for ----* *---- sorting an array of integers. ----* *---- ----* *---- ---- ---- ---- ---- ---- ---- ---- ---- ----* *---- ----* *---- Version 1.0 2016 April 1 Joseph Phillips ----* *---- ----* *--------------------------------------------------------------------------*/ #include #include #include "sortHeader.h" #define ARRAY_LEN 65536 #define TEXT_LEN 16 int array[ARRAY_LEN]; // PURPOSE: To initialize array 'array[]' of length 'arrayLen' with (pseudo-) // random values. No return value. void initializeArray (int arrayLen, int* array ) { // I. Application validity check: // II. Give 'array[]' random values. int i; for (i = 0; i < arrayLen; i++) array[i] = rand() % 1024; // III. Finished: } // PURPOSE: To exchange the element at index 'i' with that at index 'j' in // array 'array'. No return value. void exchange (int* array, int i, int j ) { // I. Application validity check: // II. Do exchange: int temp = array[i]; array[i] = array[j]; array[j] = temp; // III. Finished: } // PURPOSE: To run the integer-sorting program. Ignores command line // arguments. Returns 'EXIT_SUCCESS' to OS. int main () { initializeArray(ARRAY_LEN,array); int choice; do { char text[TEXT_LEN]; printf ("How would you like to sort %d integers: " "1: Bubble-sort " "2: Quick-sort " "Your choice? ", ARRAY_LEN ); fgets(text,TEXT_LEN,stdin); choice = atoi(text); } while ( (choice < 1) || (choice > 2) ); switch (choice) { case 1 : bubbleSort(ARRAY_LEN,array); break; case 2 : quickSort(ARRAY_LEN,array); break; } int i; for (i = 0; i < ARRAY_LEN; i++) printf("%d ",array[i]); return(EXIT_SUCCESS); } 

Header files

Hey! Ain't something missing!?! Yeah, that is right. There is no sortHeader.h.

Please write one so that you can compile the program! Please be sure to declare only what is needed in common.

Timing: Part 1

Compile and run the program without any extra optimizations, but with profiling for timing:

gcc -c bubbleSort.c gcc -c quickSort.c gcc -c sortProg.c gcc bubbleSort.o quickSort.o sortProg.o -pg -o sortO0 

Run the program twice timing it both times, and answer the following:

Function	Cumulative seconds
quickSort()	_____________
bubbleSort()	_____________

Timing: Part 2

Compile and run the program with optimization, but with profiling for timing:

gcc -c bubbleSort.c -O2 gcc -c quickSort.c -O2 gcc -c sortProg.c -O2 gcc bubbleSort.o quickSort.o sortProg.o -pg -o sortO2 -O2 

Run the program twice timing it both times, and answer the following:

Function	Cumulative seconds
quickSort()	_____________
bubbleSort()	_____________

Parts of an executable:

Please find the following inside of sortO0, either by using objdump (if it exists in the executable) or by disassembling the code and showing where the code manipulates the heap or stack. Show a disassembly or objdump.

The string "%d " in main()

The local variable temp in exchange()

The global variable array[] in sortProg.c

The code for quickSort()

Compiler optimizations:

Find and show examples at least two examples of the following optimizations in either sortO0 or sortO2.

usage of registers to hold vars (as opposed to the stack)

code motion

reduction in strength

For each optimization you find:

Tell if it exists in either sortO0, sortO2 or both, and,

Show a disassembly of the function that has it.