Advanced Data Structures please I need a full answers Assignment: Sorting Algori

Question

Advanced Data Structures

please I need a full answers

Assignment: Sorting Algorithms

Due Monday, March 27nd, 2017

The purpose of this presentation is to learn about one sorting algorithm –how it works, how it performs Big Oh, and explain it to the audience.

You will be using/writing code to test the algorithm in action as Follows:

For a given size N for your input measure the time it takes to get result. For the same N run it at least 5 times –present the average-. Let’s use int –you may try double also- as data type –easy to generate with a random generator

What to submit

Characteristics of system used

Hardware

IDE + Any comments

Example:

Processor: Intel Core 2 DUO CPU @ 2.00GHz 2.00GHz.

RAM: 2.00GB

System Type: 64-bit Operating system

Used Visual studio 2015 –Professional edition-.

Printing generated numbers from my code to the screen was time consuming. I had to eliminate that to shorten run time …………

To avoid the error I got about stack overflow. I could have changed the default setting of … It could be done by ….

Results

Note: It will take the computer a while –hours may be- as N goes up to finish, be patient !

N

Time (in seconds)

10,000

100,000

1,000,000

10,000,000

100,000,000

1,000,000,000

See how high you can go

Code Used

#include<iostream>
#include<time.h>// to use clock_t and clock()
#include<cstdlib> // to use random number generator
using namespace std;

void mySort(int array[], int n)// parameters may vary
{
   //Your code will go here
}

int main()
{
const int sizeN = 10000 then 100000 then ….; //to hold the data set size

   int *myArray = new int[sizeN];//Declaring an array of integers with size sizeN.
  
   //Populating the array
   for(int i = 0; i < sizeN ; i++)
      myArray[i] = rand(); //multiply by 1.35 or some other number for double type
     
clock_t startTime = clock();

// Call you sorting function . Arguments may differ from algorithm to algorithm
      mySort(myArray, sizeN );

// to compute its execution duration in runtime
cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;

return 0;
}

How does the sort work?

In addition to the class presentation, describe in written using an example how your algorithm work. Let’s use for that the following numbers

20, 80, 40, 25, 60, 45, 12, 7, 32

Hardware

IDE + Any comments

Example:

Processor: Intel Core 2 DUO CPU @ 2.00GHz 2.00GHz.

RAM: 2.00GB

System Type: 64-bit Operating system

Used Visual studio 2015 –Professional edition-.

Printing generated numbers from my code to the screen was time consuming. I had to eliminate that to shorten run time …………

To avoid the error I got about stack overflow. I could have changed the default setting of … It could be done by ….

Explanation / Answer

#include<iostream>
#include<time.h>// to use clock_t and clock()
#include<cstdlib> // to use random number generator
using namespace std;
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

void mySort(int array[],int l, int n)// parameters may vary
{
//Your code will go here
if (l < n)
{
/* pi is partitioning index, arr[p] is now
at right place */
int p = partition(array, l, n);

// Separately sort elements before
// partition and after partition
mySort(array, l, p - 1);
mySort(array, p + 1, n);
}
}

int main()
{
const int sizeN = 100000000; //then 100000 then ….; //to hold the data set size

int *myArray = new int[sizeN];//Declaring an array of integers with size sizeN.
  
//Populating the array
for(int i = 0; i < sizeN ; i++)
myArray[i] = rand(); //multiply by 1.35 or some other number for double type

clock_t startTime = clock();

// Call you sorting function . Arguments may differ from algorithm to algorithm
mySort(myArray,0, sizeN-1 ); // Quick sort

// to compute its execution duration in runtime
cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;

return 0;
}

for elements 20,80,40,25,60,45,12,7,32 is 0 seconds.

N TIME (in sec) 10,000 0.002 1,00,000 0.021 1,000,000 0.333 10,000,000 13.341 100,000,000 1201.51

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.