45
edits
Changes
N/A
,→Progress
Ignoring the real time spent, the majority of time is spent in the equals operator function and the class constructor, most likely because the image is constantly being manipulated, read from, and being copied to and from temporary storage for ease of use and object safety. Other than the basic functions (like read/write), it looks like the rotate and enlarge functions take a larger amount of time, which could mean that, if they were to be parallelized, it could positively affect the run time. My discernment of the big-O notation for the rotate function is O(n^2) which shows a quadratic growth rate, whereas the enlarge function had a notation of O(n^3) or greater. The reason for the rotate function having a longer run-time could be due to the fact that I enlarged the image before rotating it, but the notations don't lie. Personally, I'd say that this application is not the best for parallelization because of its simplicity in handling the images, but I can definitely see how one or more of the functions in the program can be parallelized. Some of the issues posed in making the program parallel is centered upon the image needing to be accessible to every other function, and, considering that the image is being processed, it would be constantly modified and read from. I simple terms, I think that, if multiple threads were running to quicken the program, the computation of the image could lead to errors in processing resulting in a corrupted image, distortions, and things of the sort. I may be wrong in this thought, but, to my knowledge, not being to avoid such issues makes this program somewhat difficult to safely parallelize.
'''Application 3 - Sorting Algorithms'''
'''Description:'''
I decided to select an option from the suggested projects – Sorting Algorithms. The sorting algorithms I included were: Bubble, Insertion, Selection, Merge, Heap, and Quicksort. In order to profile the sorting algorithms all at once and have a better comparison of what sorting algorithm uses the most time, I created a single module which functions that perform the sorting algorithms. I allocated memory for all of the arrays and populated a single array of size ''n'' with randomly generated data. I then copied the memory from the populated array to all of the other arrays to ensure consistency amongst the comparison of the sorting algorithms. I then passed each array to its respective sorting function which returned the sorted array using pass-by-reference. One of the things to keep in mind is that when n increases (the size of the array being sorted), the time increases. I have included 3 different profiles where n (the size of the array) equals 50000, 100000 and lastly 50000.
'''Source Code:'''
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
//Generates random numbers and assigns them to the array
void fillArray(int* arr, int size) {
for (int i = 0; i < size; i++) {
arr[i] = rand() % size;
}
}
//Performs Bubble Sort on the array passed through parameter
void bubbleSort(int *arr, int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
//Performs Selection Sort on the array passed through parameter
void selectionSort(int *arr, int size) {
for (int i = 0; i < size; i++) {
int minIdx = i;
for (int j = i; j < size; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
//swap
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
}
//Performs Insertion Sort on the array passed through parameter
void insertionSort(int *arr, int size) {
for (int i = 0; i < size; i++) {
int curr = arr[i];
int j = i;
for (j = i; j > 0 && arr[j - 1] > curr; j--) {
arr[j] = arr[j - 1];
}
arr[j] = curr;
}
}
void heapify(int *arr, int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
std::swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
//Performs Heap Sort on the array passed through parameter
//Acts as a wrapper function
void heapSort(int *arr, int size) {
// Build heap (rearrange array)
for (int i = size / 2 - 1; i >= 0; i--)
heapify(arr, size, i);
// One by one extract an element from heap
for (int i = size - 1; i >= 0; i--)
{
// Move current root to end
std::swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
//Performs Quick Sort on the array passed through parameter
void quickSort(int *arr, int left, int right) {
int leftIdx = left, rightIdx = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (leftIdx <= rightIdx) {
while (arr[leftIdx] < pivot)
leftIdx++;
while (arr[rightIdx] > pivot)
rightIdx--;
if (leftIdx <= rightIdx) {
tmp = arr[leftIdx];
arr[leftIdx] = arr[rightIdx];
arr[rightIdx] = tmp;
leftIdx++;
rightIdx--;
}
};
/* recursion */
if (left < rightIdx)
quickSort(arr, left, rightIdx);
if (leftIdx < right)
quickSort(arr, leftIdx, right);
}
//Merges the arrays and sorts it
void merge(int *arr, std::vector<int>& tmp, int start, int start2, int end) {
int lptr = start;
int rptr = start2;
int i = start;
while (lptr < start2 && rptr <= end) {
if (arr[lptr] < arr[rptr])
tmp[i++] = arr[lptr++];
else
tmp[i++] = arr[rptr++];
}
while (lptr < start2) {
tmp[i++] = arr[lptr++];
}
while (rptr <= end) {
tmp[i++] = arr[rptr++];
}
for (i = start; i <= end; i++) {
arr[i] = tmp[i];
}
}
//this function sorts arr from index start to end
void mergeIndexSort(int* arr, std::vector<int>& tmp, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeIndexSort(arr, tmp, start, mid);
mergeIndexSort(arr, tmp, mid + 1, end);
merge(arr, tmp, start, mid + 1, end);
}
}
//Acts as a wrapper function
void mergeSort(int* arr, int size) {
std::vector<int> tmp(size);
//call mergeSort with the array, the temporary
//and the starting and ending indices of the array
mergeIndexSort(arr, tmp, 0, size - 1);
}
//Print the values (Not used due to big size of array)
void print(int *arr, int size){
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main(int argc, char *argv[]) {
//Get the size of the array
int n = std::atoi(argv[1]);
// Create 6 arrays of size n and allocate memory for them
int *bubbleArray = new int[n];
int *selectionArray = new int[n];
int *insertionArray = new int[n];
int *heapArray = new int[n];
int *mergeArray = new int[n];
int *quickArray = new int[n];
//Fill the array with randomly generated numbers
fillArray(bubbleArray, n);
//print(bubbleArray, n);
//COPY the values to the other
//This adds consistency among the elements of the array
std::memcpy(selectionArray, bubbleArray, n*sizeof(int));
std::memcpy(insertionArray, bubbleArray, n * sizeof(int));
std::memcpy(heapArray, bubbleArray, n * sizeof(int));
std::memcpy(mergeArray, bubbleArray, n * sizeof(int));
std::memcpy(quickArray, bubbleArray, n * sizeof(int));
//Call the sorting algorithms 1 by 1 with their respecive array
bubbleSort(bubbleArray, n);
std::cout << "Bubble Sort performed." << std::endl;
selectionSort(selectionArray, n);
std::cout << "Selection Sort performed." << std::endl;
insertionSort(insertionArray, n);
std::cout << "Insertion Sort performed." << std::endl;
heapSort(heapArray, n);
std::cout << "Heap Sort performed." << std::endl;
mergeSort(mergeArray, n);
std::cout << "Merge Sort performed." << std::endl;
quickSort(quickArray, 0, n-1);
std::cout << "Quick Sort performed." << std::endl;
//Deallocate the arrays
delete[] bubbleArray;
delete[] selectionArray;
delete[] insertionArray;
delete[] heapArray;
delete[] mergeArray;
delete[] quickArray;
return 0;
}
'''N = 50,000'''
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
63.21 5.04 5.04 bubbleSort(int*, int)
29.91 7.42 2.38 selectionSort(int*, int)
6.79 7.96 0.54 insertionSort(int*, int)
0.13 7.97 0.01 49999 0.00 0.00 merge(int*, std::vector<int, std::allocator<int> >&, int, int, int)
0.13 7.98 0.01 quickSort(int*, int, int)
0.00 7.98 0.00 8 0.00 1.25 mergeIndexSort(int*, std::vector<int, std::allocator<int> >&, int, int)
0.00 7.98 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z9fillArrayPii
'''N = 100,000'''
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
63.91 20.05 20.05 bubbleSort(int*, int)
29.15 29.19 9.14 selectionSort(int*, int)
6.96 31.38 2.18 insertionSort(int*, int)
0.06 31.40 0.02 heapSort(int*, int)
0.03 31.41 0.01 99999 0.00 0.00 merge(int*, std::vector<int, std::allocator<int> >&, int, int, int)
0.03 31.42 0.01 quickSort(int*, int, int)
0.00 31.42 0.00 8 0.00 1.25 mergeIndexSort(int*, std::vector<int, std::allocator<int> >&, int, int)
0.00 31.42 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z9fillArrayPii
'''N = 500,000'''
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
62.36 503.32 503.32 bubbleSort(int*, int)
30.67 750.86 247.54 selectionSort(int*, int)
7.08 807.99 57.14 insertionSort(int*, int)
0.02 808.12 0.13 heapSort(int*, int)
0.01 808.20 0.08 499999 0.00 0.00 merge(int*, std::vector<int, std::allocator<int> >&, int, int, int)
0.01 808.26 0.06 quickSort(int*, int, int)
0.00 808.26 0.00 8 0.00 10.01 mergeIndexSort(int*, std::vector<int, std::allocator<int> >&, int, int)
0.00 808.26 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z9fillArrayPii
=== Assignment 2 ===
=== Assignment 3 ===
