Question

c++

#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;

Answer 1

The problem can solved by implementing the filter function:-

1. Blaze sort works with filter function it takes the pivot point as inital value of the range.

2. it arranges and finds the correct position of the first element.

3. All the elements smaller then pivot goes in left and larger one in the right side.

pseudo code: for partition
     
    step-1 : take 0th value as pivot i.e low
    initialise i = low+1 : lowest value + 1
    
    double temp -> variable for swap

    step 2 : iterate over the array
    for(j=low+1;j<=high;j++) 
    {
       swap values if arr[j]<=arr[r](i.e. pivot)
        if(arr[j]<=arr[low])
        {
            temp=arr[j];
            arr[j]=arr[i];
            arr[i]=temp;
            i++;
        }
    }
    step 3 : 
    place pivot at its position by swapping
    temp=arr[i-1];
    arr[i-1]=arr[low];
    arr[low]=temp;
    
    step 4 :
    return the pivot index
    return i-1;

Working code for filter function :

int filter(double arr[],int low,int high)
{
    int j,i=low+1;
    double temp;

    for(j=low+1;j<=high;j++)
    {
        //swap values if arr[j]<=arr[r](i.e. pivot)
        if(arr[j]<=arr[low])
        {
            temp=arr[j];
            arr[j]=arr[i];
            arr[i]=temp;
            i++;
        }
    }
    //place pivot at its position by swapping
    temp=arr[i-1];
    arr[i-1]=arr[low];
    arr[low]=temp;
    return i-1;
}

Working code for the whole program :

#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;
}
  
//Implmentation of the filter function 
int filter(double arr[],int low,int high)
{
    int j,i=low+1;
    double temp;

    for(j=low+1;j<=high;j++)
    {
        //swap values if a[j]<=a[r](i.e. pivot)
        if(arr[j]<=arr[low])
        {
            temp=arr[j];
            arr[j]=arr[i];
            arr[i]=temp;
            i++;
        }
    }
    //place pivot at its position by swapping
    temp=arr[i-1];
    arr[i-1]=arr[low];
    arr[low]=temp;
    return i-1;
}

//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;
    
    
    
}

Tested Output :