Question

In: Computer Science

#include <iostream> #include <string> #include <ctime> using namespace std; void displayArray(double * items, int start, int...

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

Solutions

Expert Solution

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

Related Solutions

#include <iostream> #include <string> #include <ctime> using namespace std; void displayArray(double * items, int start, int...
#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 =...
c++ #include <iostream> #include <string> #include <ctime> using namespace std; void displayArray(double * items, int start,...
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...
#include <iostream> #include <string> #include <array> #include <vector> using namespace std; void f(int x, int &y);...
#include <iostream> #include <string> #include <array> #include <vector> using namespace std; void f(int x, int &y); int main(){ char s1[] = "zoey"; char s2[] = "zoey"; string s3 = s1; string s4 = s2; cout << "1. sizeof(s1) = " << sizeof(s1) << endl; if(s1 == s2) cout << "2. s1 == s2 is true" << endl; else cout << "2. s1 == s2 is false" << endl; if(s3 == s4) cout << "3. s3 == s4 is true" <<...
#include<iostream> #include<cmath> using namespace std; int p = 7; void main() { extern double var ;...
#include<iostream> #include<cmath> using namespace std; int p = 7; void main() { extern double var ; int p = abs(-90); cout << ::p + p - var << endl; system("pause"); } double var = 5.5;
#include <iostream> using namespace std; const int DECLARED_SIZE = 10; void fillArray(int a[], int size, int&...
#include <iostream> using namespace std; const int DECLARED_SIZE = 10; void fillArray(int a[], int size, int& numberUsed) { cout << "Enter up to " << size << " nonnegative whole numbers.\n" << "Mark the end of the list with a negative number.\n"; int next, index = 0; cin >> next; while ((next >= 0) && (index < size)) { a[index] = next; index++; cin >> next; } numberUsed = index; } int search(const int a[], int numberUsed, int target) {...
*/ #include using namespace std; void start (int boxes [10]); void move (int squares [10], int...
*/ #include using namespace std; void start (int boxes [10]); void move (int squares [10], int x, int y, int z); void add (int arr [10], int first, int last); void print (int arr [10]); int main () {     int my_arr [10];         cout << "The original array is:\n";     print (my_arr);         start (my_arr);     cout << "\n\nThe array after start is:\n";     print (my_arr);         move (my_arr, 2, 4, 6);     cout << "\n\nThe...
#include <iostream> #include <fstream> #include <string> using namespace std; const int QUIZSIZE = 10; const int...
#include <iostream> #include <fstream> #include <string> using namespace std; const int QUIZSIZE = 10; const int LABSIZE = 10; const int PROJSIZE = 3; const int EXAMSIZE = 3; float getAverage(float arr[], int size) { float total = 0; for (int i = 0; i < size; i++) { total += arr[i]; } return total/size; } // the following main function do.... int main() { ifstream dataIn; string headingLine; string firstName, lastName; float quiz[QUIZSIZE]; float lab[LABSIZE]; float project[PROJSIZE]; float midExam[EXAMSIZE];...
#include <iostream> using namespace std; void count( int begin[], int end[] ) { int index, current[4]...
#include <iostream> using namespace std; void count( int begin[], int end[] ) { int index, current[4] = { begin[0], begin[1], begin[2], begin[3] }; add: goto print; carry: if ( current[index] < end[index] - 1 ) { current[index]++; goto add; } else if ( index > 0 ) { current[index] = begin[index]; index--; goto carry; } else return; print: cout << current[0] << current[1] << current[2] << current[3] << endl; index = 3; goto carry; } int main( ) { int...
#include <iostream> #include <stack> #include <queue> using namespace std; void printFromStack(string expr){ stack<char> myStack; for(int i=0;...
#include <iostream> #include <stack> #include <queue> using namespace std; void printFromStack(string expr){ stack<char> myStack; for(int i=0; i<expr.length(); i++){ //Insert code here to push each character onto the stack } cout << "My stack is popped in this order" << endl; while(!myStack.empty()){ //Insert code here to cout the top of the stack one by one //Pop each one after it’s printed out } cout << endl; } void printFromQueue(string expr){ queue<char> myQueue; //Insert code here to push each character onto the...
#include <iostream> #include <string> #include <fstream> #include <vector> #include <sstream> using namespace std; int main() {...
#include <iostream> #include <string> #include <fstream> #include <vector> #include <sstream> using namespace std; int main() { ifstream infile("worldpop.txt"); vector<pair<string, int>> population_directory; string line; while(getline(infile, line)){ if(line.size()>0){ stringstream ss(line); string country; int population; ss>>country; ss>>population; population_directory.push_back(make_pair(country, population)); } } cout<<"Task 1"<<endl; cout<<"Names of countries with population>=1000,000,000"<<endl; for(int i=0;i<population_directory.size();i++){ if(population_directory[i].second>=1000000000){ cout<<population_directory[i].first<<endl; } } cout<<"Names of countries with population<=1000,000"<<endl; for(int i=0;i<population_directory.size();i++){ if(population_directory[i].second<=1000000){ cout<<population_directory[i].first<<endl; } } } can u pls explain the logic behind this code up to 10 lines pls, many thanks
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT