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

Taking the 2nd example to explain -

index 2 3 4 5 6
element 43, 189, 4, 4.5, 18.35

pivot = item[2] = 43

j = 6
i = 6
item[6] = 18.35 is not greater than 43 => so do nothing

j = 5
i = 6
item[5] = 4.5 is not greater than 43 => so do nothing

j = 4
i = 6
item[4] = 4 is not greater than 43 => so do nothing

j = 3
i = 6
item[3] = 189 is greater than 43 => so swap item[6] and item[3] and decrement i // swap item[i] & item[j]
Now array is -> 43 18.35 4 4.5 189

j = 2 => exit the for loop
i = 5

now put the pivot element to the right position
swap item[5] and item[2] -> swap item[start] and item[i]
so now the array is -> 4.5 18.35 4 43 189

/* take the first element as pivot and do partition */

float filter(float items[], int start, int end){
float pivot = items[start];
int i = end;
for(int j = end; j > low; j--){
if(arr[j] > pivot){
float temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
end--;
}
}

float temp = item[i];
item[i] = item[start];
item[start] = temp;
return i;
}

The time taken depends upon the input array

1. Worst Case - When the first element (pivot element) is either the smallest or the largest element of the array -> O(n^2)

2. Best Case - When the middle emenet is picked as pivot -> O(n*Logn)
n is the no. of element -> for traversing through n elements
Logn -> for partitioning
Can be resolved fully using the Master Theorem used for BigO calculation

Additional Note : This sorting is actually called Quick Sort.

whale.txt -> is not available
To convert this logic to String, instead of float create an array of String and use String's comparison method.
In case of java the method compareTo() can be used to compare 2 strings lexicographically.
If both the strings are equal then this method returns 0. If the first string is lexicographically greater than the second string, it returns positive number else the result would be negative.

In case of C++ strcmp() can be used instead of > symbol used to compare with pivot element