== Team Members ==
# [mailto:wwpark@myseneca.ca?subject=DPS915 Woosle Park], Data Compression
# [mailto:jpitters@myseneca.ca?subject=DPS915 Jordan Pitters], Image Processing
# [mailto:apatel271@myseneca.ca?subject=DPS915 Akshat Patel], Sorting Algorithms
# [mailto:jpitters@myseneca.ca?subject=DPS915 Jordan Pitters], Image Processing
[mailto:jpitters@myseneca.ca;wwpark@myseneca.ca?subject=DPS915;apatel271@myseneca.ca?subject=DPS915 Email All];
This of time is spent in the compress function and the hashtable takes up most of the time because it is constantly being manipulated and read from. It looks like if the hashtable and the compress function were to be parallelized about 90% of the run time would be affected. The big-O for the application should be O(n) time so there is a linear increase in time based on file size, however the hashtable grew more in time compared to the compress function the larger the file. This application is not good for parallelization because of the dictionary hashtable. Due to the hastable or the compress dictionary needing to be accessible globally and be constantly modifiable and read this could pose issues if multiple threads were running especially since modifying and reading the table needs to be done sequentially for efficient compression. Threading the compress could lead to errors in compressions making this difficult to 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, Heap, Merge, Heap, and Quicksort. In order I decided to profile create an application that uses all of the sorting algorithms all at once and have calls their respective functions instead of creating individual modules and profiling them, simply because the 99% percent of the total running time would be taken up by the sorting algorithm function. So for a better understanding and comparison of what the time taken by each sorting algorithm uses the most time, I created decided to create a single module which with 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 consistent data throughout all 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 arrayvoid fillArray(int* arr, int size) { for (int i = 0; i < size; i++) { arr[i] = rand() % size; }} //Performs Bubble Sort on the array passed through parametervoid 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 + 1File:SortingAlgorithms.cpp.txt]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } }} //Performs Selection Sort on The link to the source code AND the array passed through parametervoid 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 make file can also be found on the array passed through parametervoid 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]; } arrGitHub at: [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) { stdhttps::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 functionvoid heapSort(int *arr, int size) { // Build heap (rearrange array) for (int i = size / 2 - 1; i >= 0; i--) heapify(arr, size, i); github.com/Akshat55/ One by one extract an element from heap for (int i = size Sorting- 1; i >= 0; iAlgorithms--) { // Move current root to end stdComparison https::swap(arr[0], arr[i]); // call max heapify on the reduced heap heapify(arr, i, 0); }} github.com/Akshat55/Performs Quick Sort on the array passed through parametervoid 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++; rightIdxSorting-Algorithms-; } }; /* recursion */ if (left < rightIdx) quickSort(arr, left, rightIdx); if (leftIdx < right) quickSort(arr, leftIdx, right);} //Merges the arrays and sorts itvoid 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++Comparison]; } while (lptr < start2) { tmp[i++] = arr[lptr++]; } while (rptr <= end) { tmp[i++] = arr[rptr++]; } for (i = start; i <= end; i++) { arr[i] = tmp[i]; }}
'''N = 50,000'''
Total Time (seconds) = 7.98 seconds
//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:
'''N = 100,000'''
Total Time (seconds) = 31.42 seconds
Flat profile:
'''N = 500,000'''
Total Time (minutes) = 13.47 minutes
Flat profile:
0.00 808.26 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z9fillArrayPii
'''Conclusion:'''
Based on the results from profiling 3 different sizes of arrays, we can assume that majority of the time taken to sort the arrays is taken by the O(n^2) algorithms (Bubble, Insertion, and Selection). However, the other sorting algorithms (Heap, Merge, Quick) that are O(n log(n)) are extremely fast even when the size of the arrays are large. As observed from the profile, the elapsed time increased as the size of the array increased. I went from approximately 8 seconds to execute the entire program to 13 minutes to execute.
----
'''Final Selection: Sorting Algorithms'''
Based on the profiled applications above, we think that the sorting algorithms would benefit a lot from offloading to the GPU. Sorting Algorithms are commonly used in programming and can have a strong impact on the programs speed and efficiency. Since they are so commonly used, we think it would be quite interesting to see if we can speed up the O(n^2) sorting algorithms to potentially match the sorting speed of the O(n log n) algorithms since there won’t much change for the parallelized version of them, as they are already fast.
=== Assignment 2 ===
=== Assignment 3 ===
