Answered: Create a second version of Blaze Sort…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

100%

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

}

```cpp
////////////////////////////////////////////////////////////////////
// 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;
```

This code snippet is from a sorting algorithm implementation designed to evaluate the performance and correctness of "Blaze Sort." The code is divided into different parts for thorough testing and analysis:

- **Part 2:** The code tests if Blaze Sort can correctly sort a predefined array of doubles.

- **Part 3:** This section is a stress test to measure the speed of Blaze Sort with larger arrays. It hints at using different array sizes and involves clocking the sorting operation to determine its efficiency in milliseconds.

- **

```cpp
#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)
//Hmm... 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.
// 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.

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions