Question

#include <iostream>
#include <string>
#include <ctime>
using namespace std;


void displayArray(double * items, int start, int end)
{
        for (int i = start; i <= end; i++)
                cout << items[i] << " ";
        cout << endl;
}



//The legendary "Blaze Sort" algorithm.
//Sorts the specified portion of the array between index start and end (inclusive)
//Hmmm... how fast is it?
/*
void blazeSort(double * items, int start, int end)
{
        if (end - start > 0)
        {
                int p = filter(items, start, end);
                blazeSort(items, start, p - 1);
                blazeSort(items, p + 1, end);
        }
}
*/

int main()
{
        ////////////////////////////////////////////////////
        //Part 1:  Implement a method called filter.
        ////////////////////////////////////////////////////

        //Filter is a function that takes in an array and a range (start and end).
        //
        //Call the first item in the range the 'pivot'.
        //
        //Filter's job is to simply separate items within the range based on whether they are bigger or smaller than the pivot.
        //In the example array below, 13 is the pivot, so all items smaller than 13 are placed in indices 0-3.  The pivot is then placed at index 4, and all
        //remaining items, which are larger than the pivot, are placed at positions 5-10.  Note that the array is NOT sorted, just "partitioned" around
        //the pivot value.  After doing this, the function must return the new index of the pivot value.

        double testNumsA[] = { 13, 34.1, 43, 189, 4, 4.5, 18.35, 85, 3, 37.2, 5 };

        //The filter will place all items <= 13 to the left of value 13, and all items large than 13 to the right of 13 in the array.
        int p = filter(testNumsA, 0, 10);
        cout << p << endl; //should be 4, the new index of 13.
        displayArray(testNumsA, 0, 10);  //should display something like this:  5 3 4.5 4 13 18.35 85 189 37.2 43 34.1

        //One more example:
        double testNumsB[] = { 13, 34.1, 43, 189, 4, 4.5, 18.35, 85, 3, 37.2, 5 };
        p = filter(testNumsB, 2, 6);  //Here we are only interested in items from indices 2-6, ie, 43, 189, 4, 4.5, 18.35
        cout << p << endl; //should be 5
        displayArray(testNumsB, 0, 10); //Notice only indices 2-6 have been partioned:  13 34.1 18.35 4 4.5 43 189 85 3 37.2 5


        /////////////////////////////////////////////////////////////////////////////////
        //Part 2:  Uncomment "Blaze Sort".
        //Blaze Sort uses/needs your filter to work properly.
        /////////////////////////////////////////////////////////////////////////////////


        //Test if Blaze Sort correctly sorts the following array.
        double testNums[] = { 13, 34.1, 43, 189, 4, 4.5, 18.35, 85, 3, 37.2, 5 };

        blazeSort(testNums, 0, 10);

        displayArray(testNums, 0, 10);

        /////////////////////////////////////////////////////////////////////
        //Part 3:  Test how fast Blaze Sort is for large arrays.
        //What do you think the run-time (big-Oh) of blaze sort is?
        /////////////////////////////////////////////////////////////////////

        //Stress test:
        int size = 100; //test with: 1000, 10000, 100000,1000000, 10000000
        double * numbers = new double[size];

        for (int i = 0; i < size; i++)
        {
                numbers[i] = rand();
        }

        clock_t startTime, endTime;

        startTime = clock();
        blazeSort(numbers, 0, size - 1);
        endTime = clock();

        displayArray(numbers, 0, size - 1);
        cout << "Blaze sort took: " << endTime - startTime << " milliseconds to sort " << size << " doubles."  << endl;

        ////////////////////////////////////////////////////////////////////
        //Part 4: Sort Moby Dick, but this time with Blaze Sort
        ///////////////////////////////////////////////////////////////////

        //////////////////////////////////////////////////////////////////
        //1) Create a second version of Blaze Sort that sorts arrays of strings
        //(instead of arrays of doubles).
        //2) Download whale.txt from the previous lab.  Read the words from the file into
        //an array, sort the array with Blaze Sort, and then write the sorted words to an output file.
        //
        //This time, it has to be fast!  Must finish in under 10 seconds.
        /////////////////////////////////////////////////////////////////

        return 0;
}

Answer 1

#include <iostream>
#include <string>
#include <ctime>
#include <fstream>
#include <vector> 
using namespace std;


void displayArray(double * items, int start, int end)
{
    for (int i = start; i <= end; i++)
            cout << items[i] << " ";
    cout << endl;
}



//The legendary "Blaze Sort" algorithm.
//Sorts the specified portion of the array between index start and end (inclusive)
//Hmmm... how fast is it?

int filter(double * items, int start, int end){
    int i = end+1;
    
    int pivot = start; //selecting the first element as the pivot element
    for( int j = end; j>= start; j--){
        if( items[j] > items[pivot] ){ //if the element is greater than the pivot element then mocing it to the end of the array
            i--;
            double temp = items[i];
            items[i] = items[j];
            items[j] = temp;
        }
    }
    // uptil i all the element are greater than the pivot element
    i--;

    double temp = items[pivot];
    items[pivot] = items[i];
    items[i] = temp;
    return i;
}

void blazeSort(double * items, int start, int end)
{
    if (end - start > 0)
    {
            int p = filter(items, start, end);
            blazeSort(items, start, p - 1);
            blazeSort(items, p + 1, end);
    }
}

// modified blaze sort for strings
int filterString(string * items, int start, int end){
    int i = end+1;
    
    int pivot = start; //selecting the first element as the pivot element
    for( int j = end; j>= start; j--){
        if( items[j] > items[pivot] ){ //if the element is greater than the pivot element then mocing it to the end of the array
            i--;
            string temp = items[i];
            items[i] = items[j];
            items[j] = temp;
        }
    }
    // uptil i all the element are greater than the pivot element
    i--;

    string temp = items[pivot];
    items[pivot] = items[i];
    items[i] = temp;
    return i;
}

void blazeSortString(string * items, int start, int end)
{
    if (end - start > 0)
    {
            int p = filterString(items, start, end);
            blazeSortString(items, start, p - 1);
            blazeSortString(items, p + 1, end);
    }
}


int main()
{
        ////////////////////////////////////////////////////
        //Part 1:  Implement a method called filter.
        ////////////////////////////////////////////////////

        //Filter is a function that takes in an array and a range (start and end).
        //
        //Call the first item in the range the 'pivot'.
        //
        //Filter's job is to simply separate items within the range based on whether they are bigger or smaller than the pivot.
        //In the example array below, 13 is the pivot, so all items smaller than 13 are placed in indices 0-3.  The pivot is then placed at index 4, and all
        //remaining items, which are larger than the pivot, are placed at positions 5-10.  Note that the array is NOT sorted, just "filtered" around
        //the pivot value.  After doing this, the function must return the new index of the pivot value.

        double testNumsA[] = { 13, 34.1, 43, 189, 4, 4.5, 18.35, 85, 3, 37.2, 5 };

        //The filter will place all items <= 13 to the left of value 13, and all items large than 13 to the right of 13 in the array.
        int p = filter(testNumsA, 0, 10);
        cout << p << endl; //should be 4, the new index of 13.
        displayArray(testNumsA, 0, 10);  //should display something like this:  5 3 4.5 4 13 18.35 85 189 37.2 43 34.1

        //One more example:
        double testNumsB[] = { 13, 34.1, 43, 189, 4, 4.5, 18.35, 85, 3, 37.2, 5 };
        p = filter(testNumsB, 2, 6);  //Here we are only interested in items from indices 2-6, ie, 43, 189, 4, 4.5, 18.35
        cout << p << endl; //should be 5
        displayArray(testNumsB, 0, 10); //Notice only indices 2-6 have been partioned:  13 34.1 18.35 4 4.5 43 189 85 3 37.2 5


        /////////////////////////////////////////////////////////////////////////////////
        //Part 2:  Uncomment "Blaze Sort".
        //Blaze Sort uses/needs your filter to work properly.
        /////////////////////////////////////////////////////////////////////////////////


        //Test if Blaze Sort correctly sorts the following array.
        double testNums[] = { 13, 34.1, 43, 189, 4, 4.5, 18.35, 85, 3, 37.2, 5 };

        blazeSort(testNums, 0, 10);

        displayArray(testNums, 0, 10);

        /////////////////////////////////////////////////////////////////////
        //Part 3:  Test how fast Blaze Sort is for large arrays.
        //What do you think the run-time (big-Oh) of blaze sort is?
        /////////////////////////////////////////////////////////////////////
        // Time taken by BlazeSort in general can be written as following.

        // T(n) = T(k) + T(n-k-1) + θ(n)
        // The first two terms are for two recursive calls, the last term is for the filter process. k is the number of elements which are smaller than pivot.
        // The time taken by BlazeSort depends upon the input array and filter strategy. Following are three cases.

        //     Worst Case: 
        //         The worst case occurs when the filter process always picks greatest or smallest element as pivot. If we consider above filter strategy where last element is always picked as pivot, the worst case would occur when the array is already sorted in increasing or decreasing order. Following is recurrence for worst case.

        //         T(n) = T(0) + T(n-1) + θ(n)
        //         which is equivalent to  
        //         T(n) = T(n-1) + θ(n)
        //         The solution of above recurrence is θ(n2).

        //     Best Case: 
        //         The best case occurs when the filter process always picks the middle element as pivot. Following is recurrence for best case.

        //         T(n) = 2T(n/2) + θ(n)
        //         The solution of above recurrence is θ(nLogn). It can be solved using case 2 of Master Theorem.

        //     Average Case:
        //         To do average case analysis, we need to consider all possible permutation of array and calculate time taken by every permutation which doesn’t look easy.
        //         We can get an idea of average case by considering the case when filter puts O(n/9) elements in one set and O(9n/10) elements in other set. Following is recurrence for this case.

        //         T(n) = T(n/9) + T(9n/10) + θ(n)
        //         Solution of above recurrence is also O(nLogn)

        //     Although the worst case time complexity of BlazeSort is O(n2) which is more than many other sorting algorithms like Merge Sort and Heap Sort, BlazeSort is faster in practice, because its inner loop can be efficiently implemented on most architectures, and in most real-world data. BlazeSort can be implemented in different ways by changing the choice of pivot, so that the worst case rarely occurs for a given type of data. However, merge sort is generally considered better when data is huge and stored in external storage.



        //Stress test:
        int size = 100; //test with: 1000, 10000, 100000,1000000, 10000000
        double * numbers = new double[size];

        for (int i = 0; i < size; i++)
        {
                numbers[i] = rand();
        }

        clock_t startTime, endTime;

        startTime = clock();
        blazeSort(numbers, 0, size - 1);
        endTime = clock();

        displayArray(numbers, 0, size - 1);
        cout << "Blaze sort took: " << endTime - startTime << " milliseconds to sort " << size << " doubles."  << endl;

        ////////////////////////////////////////////////////////////////////
        //Part 4: Sort Moby Dick, but this time with Blaze Sort
        ///////////////////////////////////////////////////////////////////

        //////////////////////////////////////////////////////////////////
        //1) Create a second version of Blaze Sort that sorts arrays of strings
        //(instead of arrays of doubles).
        //2) Download whale.txt from the previous lab.  Read the words from the file into
        //an array, sort the array with Blaze Sort, and then write the sorted words to an output file.
        //
        //This time, it has to be fast!  Must finish in under 10 seconds.
        /////////////////////////////////////////////////////////////////
        ofstream resultFile; // output file to store the result
        resultFile.open ("resultFile.txt"); 
        ifstream inFile("whale.txt"); // opening the input file
        if(inFile.is_open()) 
        {
            vector<string> data; 

            while ( !inFile.eof() ) // reading until we reach to the dn of file
            {
                string temp;
                inFile >> temp;
                data.push_back(temp); //storing the string in the vector for the dynamic length array
            }
            int size = data.size();
            string dataArray[size];

            std::copy(data.begin(), data.end(), dataArray); //converting the vector to the array for sorting

            blazeSortString( dataArray,0 ,size -1 ); // sorting the array with the modified blaze sort for strings

            for( int i = 0; i< size; i++){
                resultFile << dataArray[i] << endl; //writing our result to the file
            }

            resultFile.close();
            inFile.close();
        }
        
        
        return 0;
        
}