Untitled

/*
  Name: Programming Lab#03 Template
  Copyright:
  Author: Dr. Chang-Sheng Chen, <cschen@mail.nctu.edu.tw>
  Date: 19/03/11 10:13
  Description: In this lab, we would like to practice the following:
               a. passing values of an entire array to functions (e.g., function argument using pass-by-reference)
               b. modifying the elements values of a array in called functions
               c. practicing the recusive problem-solving method by using the recursive function calls
                  * attacked problem: to sort a small list of integers stored in an array
                  * method: recusive insertion sort, recursive selection sort
*/
#include <cstdlib>
#include <iostream>
#include <ctime>  // srand(seed) function might use the time(0) function, which requires the header file

using namespace std;

// Required function prototypes - you must define the following functions
int preSort (int[], const int); // before sorting: prepare (or determine) the required parameters
int preSort (int[], int[], const int, bool &);
void postSort(int[], const int); // after sort: display the sorting result

void littledotIsTooHandsome(int [], int, int, int);

int insertionSort_rec(int[], const int, int, const bool);
int selectionSort_rec(int [], const int, int, const bool);

// Optional function prototypes - you might want to define the following functions
void displayArrayElements(int [], const int);
void swapArrayElements (int &, int &);

// If you finish the above programming lab early, you could try design the iterated version
int insertionSort_loop(int[], const int, const bool);  // we have a similar version defined in the textbook
int selectionSort_loop(int [], const int, const bool);

// No global variables are permitted in this programming lab !!!!

int main(int argc, char *argv[])
{
   // Testing Array and the list of its element - use the following to test your functions
   const int arraySizeT = 10;
   int arrayT[arraySizeT] = {10, 55, 33, 21, 67, 87, 24, 5, 35, 72};

   const int arraySizeB = 7;
   int arrayB[arraySizeB] = {};
   bool ascendingOrder =1 ; // 1 == ascending, 0 == descending
   int startS=0; // start element to trigger next sorting sub-process
   int targetV=0; // returned target value, after the determined sorting is done

   // Step1 (15%): define (design) a function, preSort, to accomplish the following:
   // -------------------------------------------------------------------------------------------------------
   //        a. Given an integer arrayB with the specified size value(i.e., bSize), generate and store the list
   //           of elements in the arrayB
   //
   //        b. determine the method of recursive sorting and the sorting order  by a random function (or a
   //           set of function; e.g., simulating the coin-tossing and/or the dice-rolling process).
   //           * recursive sorting method - 0: insertion sort, 1: selection sort, 2: other sort(Not defined in this Lab)
   //           * sorting order - 0: ascending, 1: descending ;
   //=============================================================================================
    srand(time(0));

    displayArrayElements(arrayB, arraySizeB);
    int sortingMethod = preSort(arrayT, arrayB, arraySizeB, ascendingOrder);
    printf("sortingMethod=%d ascendingOrder=%d\n", sortingMethod, ascendingOrder);


   // Step2 (10%):By using the result of the preSort function, define a function to display the initialing factors:
   //---------------------------------------------------------------------------------------------------------------
   //          a. the recursive sorting method to use
   //          b. the sorting order
   //          c. showing the values of the unsorted array
   //        For example, here is a possible output sequence:
   //             "We are doing a recursive selection sort in descending order !!! <newline>"
   //             "Unsorted array: <newline>"
   //               arrayB[0] = 11
   //               arrayB[1] = 35
   //               ...  (list of required elements of the array)
   //=======================================================================================================

    littledotIsTooHandsome(arrayB, arraySizeB, ascendingOrder, sortingMethod);

    // Step 3(70%=2*35%): define two recursive functions, with the 4 required parameters, to accomplish the following:
    //-----------------------------------------------------------------------------------------------------------
    //       i.e., sort the arrayB and return the target value (i.e., minimun or maximun value of the array)
    //        * methods: recursive insertion sort or recursive selection sort

        // targetV = insertionSort_rec (arrayA, arraySizeA, startS, ascendingOrder);
        // targetV = selectionSort_rec(arrayB, arraySizeB, startS, ascendingOrder); // start from the 1st element
        // targetV = selectionSort_loop(arrayB, arraySizeB);


    // Step 4 (5%) - define a postSort function, to show the result of the sorting:
    //-------------------------------------------------------------------------------
    //         a. the sorted array
    //         b. the expected target value (i.e., maximum, if sorting in ascending; otherwise, minimum.)


    system("PAUSE");
    return EXIT_SUCCESS;
}


// littledot: The presort function, note that I have OVERLOADED the original function !!!
//            Check with TA to see if overloading is allowed !!!
int preSort (int arrT[], int arrB[], const int bSize, bool &order){
    for(int i=0; i<bSize; i++)
        swapArrayElements(arrT[i], arrB[i]);

    order = rand() % 2;
    return rand() % 2;
}

// littledot: Reports the current status
void littledotIsTooHandsome(int arrB[], int bSize, int order, int method){
    char orderStr[50], methodStr[50];

    if(order==1)strcpy(orderStr, "ascending");
    else strcpy(orderStr, "descending");

    if(method==1)strcpy(methodStr, "insertion");
    else strcpy(methodStr, "selection");

    printf("We are doing a recursive %s sort in %s order !!!\n",methodStr, orderStr);
    printf("Unsorted array:\n");
    displayArrayElements(arrB, bSize);
}


int insertionSort_rec (int b[], const int bSize, int next, const bool ascendingOrder)
{
     int targetV=0;

     //step1: basic case checking, is there any remaining element to insert ?
     //        if NO, finish and return the last element value of the array b;

     //step2: insert the j element into the other sorted sub-array with j-1 elements
     //       * next - the next element to insert; start of the unsorted sub-array

     //Step3: recursively called the function itself to continue processing
              // Or, if next element is not the last element, recursively called the function again

 return  targetV;
}


int selectionSort_rec(int b[], const int bSize, int start, const bool ascendingOrder)
{
  int targetV=0;

    //step1: basic case checking, is the last element of the array ?
     //        if YES (aleardy sorted), finish and return the last element value of the array b;

     //step2: find the target value by selecting from the unsorted sub-array beginging from the elementt
     //        with the index <start>
     //       * start - start of the unsorted sub-array

     //Step3: recursively called the function itself to continue processing
              // Or, if next element is not the last element, recursively called the function again

    return  targetV;
 }


// Optional- you might want to define the following functions
//------------------------------------------------------------
void displayArrayElements(int b[], const int size)
{    for(int i=0; i<size; i++)
        printf("arr[%d]=%d\n",i,b[i]);
}

void swapArrayElements(int &a, int &b)
{
    printf("before swapping:%d(%x)=%d\t%d(%x)=%d\n",&a,&a,a,&b,&b,b);

    int temp = a;
    a = b;
    b = temp;

    printf("after swapping:\t%d(%x)=%d\t%d(%x)=%d\n",&a,&a,a,&b,&b,b);
}


// If you finish the above programming lab early, you could try design the iterated version
//------------------------------------------------------------------------------------------
int insertionSort_loop (int b[], const int size, const bool ascendingOrder)
{
    int targetV=0;
    // To define the missing part
    return  targetV;
}

int selectionSort_loop(int b[], const int bSize, const bool ascendingOrder )
{
    int targetV=0;
    // To define the missing part
    return  targetV;
}