N/A
Team Members
- Woosle Park, Data Compression
- Akshat Patel, Sorting Algorithms
- Jordan Pitters, Image Processing
Progress
Assignment 1
Application 1 - Data Compression
Description: https://www.geeksforgeeks.org/lzw-lempel-ziv-welch-compression-technique/
The algorithm used for data compression here is the Lempel–Ziv–Welch (LZW) algorithm. It is a lossless algorithm meaning no data is lost during compression for a file. This algorithm is generally used for gif or pdf files but for this example, I used a .txt file because it was easier to manipulate and scale in size. The file used for compression is a .txt version of the Holy Bible(https://raw.githubusercontent.com/mxw/grmr/master/src/finaltests/bible.txt) because the contents are large enough to see the compression time and percentage. The algorithm should read a files sequence of symbols and grouping them into strings and then converting it into bit 12 code that is then stored into a table. That table is then referred to when decompressing a file doing a reverse sequence of steps from compression.
Source Code:
// Compile with gcc 4.7.2 or later, using the following command line:
//
// g++ -std=c++0x lzw.c -o lzw
//
//LZW algorithm implemented using fixed 12 bit codes.
#include <iostream>
#include <sstream>
#include <fstream>
#include <bitset>
#include <string>
#include <unordered_map>
#define MAX_DEF 4096
using namespace std;
string convert_int_to_bin(int number)
{
string result = bitset<12>(number).to_string();
return result;
}
void compress(string input, int size, string filename) {
unordered_map<string, int> compress_dictionary(MAX_DEF);
//Dictionary initializing with ASCII
for ( int unsigned i = 0 ; i < 256 ; i++ ){
compress_dictionary[string(1,i)] = i;
}
string current_string;
unsigned int code;
unsigned int next_code = 256;
//Output file for compressed data
ofstream outputFile;
outputFile.open(filename + ".lzw");
for(char& c: input){
current_string = current_string + c;
if ( compress_dictionary.find(current_string) ==compress_dictionary.end() ){
if (next_code <= MAX_DEF)
compress_dictionary.insert(make_pair(current_string, next_code++));
current_string.erase(current_string.size()-1);
outputFile << convert_int_to_bin(compress_dictionary[current_string]);
current_string = c;
}
}
if (current_string.size())
outputFile << convert_int_to_bin(compress_dictionary[current_string]);
outputFile.close();
}
void decompress(string input, int size, string filename) {
unordered_map<unsigned int, string> dictionary(MAX_DEF);
//Dictionary initializing with ASCII
for ( int unsigned i = 0 ; i < 256 ; i++ ){
dictionary[i] = string(1,i);
}
string previous_string;
unsigned int code;
unsigned int next_code = 256;
//Output file for decompressed data
ofstream outputFile;
outputFile.open(filename + "_uncompressed.txt");
int i =0;
while (i<size){
//Extracting 12 bits and converting binary to decimal
string subinput = input.substr(i,12);
bitset<12> binary(subinput);
code = binary.to_ullong();
i+=12;
if ( dictionary.find(code) ==dictionary.end() )
dictionary.insert(make_pair(code,(previous_string + previous_string.substr(0,1))));
outputFile<<dictionary[code];
if ( previous_string.size())
dictionary.insert(make_pair(next_code++,previous_string + dictionary[code][0]));
previous_string = dictionary[code];
}
outputFile.close();
}
string convert_char_to_string(const char *pCh, int arraySize){
string str;
if (pCh[arraySize-1] == '\0') str.append(pCh);
else for(int i=0; i<arraySize; i++) str.append(1,pCh[i]);
return str;
}
static void show_usage()
{
cerr << "Usage: \n"
<< "Specify the file that needs to be compressed or decompressed\n"
<<"lzw -c input #compress file input\n"
<<"lzw -d input #decompress file input\n"
<<"Compressed data will be found in a file with the same name but with a .lzw extension\n"
<<"Decompressed data can be found in a file with the same name and a _uncompressed.txt extension\n"
<< endl;
}
int main (int argc, char* argv[]) {
streampos size;
char * memblock;
if (argc <2)
{
show_usage();
return(1);
}
ifstream file (argv[2], ios::in|ios::binary|ios::ate);
if (file.is_open())
{
size = file.tellg();
memblock = new char[size];
file.seekg (0, ios::beg);
file.read (memblock, size);
file.close();
string input = convert_char_to_string(memblock,size);
if (string( "-c" ) == argv[1] )
compress(input,size, argv[2]);
else if (string( "-d" ) == argv[1] )
decompress(input,size, argv[2]);
else
show_usage();
}
else {
cout << "Unable to open file."<<endl;
show_usage();
}
return 0;
}
Flatline Profiles:
bible.txt - 4,351,186 bytes
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls ns/call ns/call name 50.04 0.18 0.18 5758089 31.29 31.29 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_find_before_node(unsigned long, std::string const&, unsigned long) const 50.04 0.36 0.18 compress(std::string, int, std::string) 0.00 0.36 0.00 1402806 0.00 31.29 std::__detail::_Map_base<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true>, true>::operator[](std::string const&) 0.00 0.36 0.00 4098 0.00 0.00 show_usage() 0.00 0.36 0.00 4097 0.00 0.00 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_insert_unique_node(unsigned long, unsigned long, std::__detail::_Hash_node<std::pair<std::string const, int>, true>*) 0.00 0.36 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z18convert_int_to_bini 0.00 0.36 0.00 1 0.00 0.00 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::clear()
bible2.txt - 8,702,373 bytes
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls ns/call ns/call name 48.39 0.44 0.44 11511109 38.26 38.26 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_find_before_node(unsigned long, std::string const&, unsigned long) const 46.19 0.86 0.42 compress(std::string, int, std::string) 5.50 0.91 0.05 2804639 17.84 56.10 std::__detail::_Map_base<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true>, true>::operator[](std::string const&) 0.00 0.91 0.00 4098 0.00 0.00 show_usage() 0.00 0.91 0.00 4097 0.00 0.00 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_insert_unique_node(unsigned long, unsigned long, std::__detail::_Hash_node<std::pair<std::string const, int>, true>*) 0.00 0.91 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z18convert_int_to_bini 0.00 0.91 0.00 1 0.00 0.00 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::clear()
bible3.txt - 13,053,560 bytes
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls ns/call ns/call name 47.58 0.58 0.58 17264129 33.63 33.63 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_find_before_node(unsigned long, std::string const&, unsigned long) const 42.66 1.10 0.52 compress(std::string, int, std::string) 7.38 1.19 0.09 4206472 21.41 55.04 std::__detail::_Map_base<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true>, true>::operator[](std::string const&) 1.64 1.21 0.02 convert_char_to_string(char const*, int) 0.82 1.22 0.01 std::pair<std::__detail::_Node_iterator<std::pair<unsigned int const, std::string>, false, false>, bool> std::_Hashtable<unsigned int, std::pair<unsigned int const, std::string>, std::allocator<std::pair<unsigned int const, std::string> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::_M_emplace<std::pair<unsigned int, std::string> >(std::integral_constant<bool, true>, std::pair<unsigned int, std::string>&&) 0.00 1.22 0.00 4098 0.00 0.00 show_usage() 0.00 1.22 0.00 4097 0.00 0.00 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_insert_unique_node(unsigned long, unsigned long, std::__detail::_Hash_node<std::pair<std::string const, int>, true>*) 0.00 1.22 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z18convert_int_to_bini 0.00 1.22 0.00 1 0.00 0.00 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::clear()
bible4.txt - 17,039,360 bytes
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls ns/call ns/call name 60.43 0.96 0.96 22530032 42.65 42.65 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_find_before_node(unsigned long, std::string const&, unsigned long) const 32.73 1.48 0.52 compress(std::string, int, std::string) 6.29 1.58 0.10 5486575 18.24 60.89 std::__detail::_Map_base<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true>, true>::operator[](std::string const&) 0.63 1.59 0.01 convert_char_to_string(char const*, int) 0.00 1.59 0.00 4098 0.00 0.00 show_usage() 0.00 1.59 0.00 4097 0.00 0.00 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_insert_unique_node(unsigned long, unsigned long, std::__detail::_Hash_node<std::pair<std::string const, int>, true>*) 0.00 1.59 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z18convert_int_to_bini 0.00 1.59 0.00 1 0.00 0.00 std::_Hashtable<std::string, std::pair<std::string const, int>, std::allocator<std::pair<std::string const, int> >, std::__detail::_Select1st, std::equal_to<std::string>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::clear()
Conclusion:
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 2 - Image Processing
Description:
The code in focus was borrowed from user "cwginac" at DreamInCode:
cwginac - Image Processing Tutorial
I stumbled across this code while searching for a program written in C++ that holds the purpose of processing images, and can be deployed on Linux without too many issues with libraries. I began my research looking for open source image processing programs, which lead me to a number of libraries and sources, (including CLMG). However, those sources were mainly in JAVA. Concerned that I didn't truly understand the process, I then redefined my focus to understanding image processing. I thus searched for "image processing tutorials in C++". The DreamInCode website was one that was listed on the front page. The code uses standard libraries to handle images in the PGM format. It is a fairly straight forward program that intakes a number of images as command-line arguments, with the first being the image to edit, and provides the user some options to process the image, outputting the result to one of the provided image paths. The one thing I noticed the program lacks is a method for converting images to PGM, considering the program requires it. Therefore, for my testing of the program, I took a JPEG image and converted it to PGM using an online method found here: Dan's Tools - Convert Files. Providing just the one image as a command-line argument only yielded 4 options that include getting/setting the values of pixels and getting other information. Looking through the code I knew there was more to it, but the method to process an image using the program required 2 arguments: first is the original image, second is the output image. With these provided, the program allows the user to rotate, invert/ reflect, enlarge, shrink, crop, translate, and negate.
The code is found on the site, near the end of the article. To run it, I made a Makefile. The code downloaded and borrowed from the site are stored as text files, so I renamed them as .cpp and .h files within the Linux environment.
Here are the files for ease of access: File:Main.cpp.txt | File:Image.h.txt | File:Image.cpp.txt
Also, here is the Makefile:
#Makefile for A1 - Image Processing
#
GCC_VERSION = 8.2.0
PREFIX = /usr/local/gcc/${GCC_VERSION}/bin/
CC = ${PREFIX}gcc
CPP = ${PREFIX}g++
main: main.o
$(CPP) -pg -omain main.o
main.o: main.cpp
$(CPP) -c -O2 -g -pg -std=c++17 main.cpp image.cpp
clean:
rm *.o
From my test, I used a 768 KB image borrowed from the web, enlarged it a couple times, shrank it, rotated it, and negated it. The result was an 18.7 MB image. The time it took to run the program was:
real 1m33.427s user 0m0.431s sys 0m0.493s
The generated FLAT profile of the program revealed:
% cumulative self self total time seconds seconds calls ms/call ms/call name 34.46 0.21 0.21 7 30.03 30.03 Image::operator=(Image const&) 26.26 0.37 0.16 6 26.69 26.69 Image::Image(int, int, int) 13.13 0.45 0.08 Image::rotateImage(int, Image&) 11.49 0.52 0.07 writeImage(char*, Image&) 9.85 0.58 0.06 Image::enlargeImage(int, Image&) 1.64 0.59 0.01 readImage(char*, Image&) 1.64 0.60 0.01 Image::negateImage(Image&) 1.64 0.61 0.01 Image::shrinkImage(int, Image&) 0.00 0.61 0.00 7 0.00 0.00 Image::~Image() 0.00 0.61 0.00 1 0.00 0.00 _GLOBAL__sub_I__ZN5ImageC2Ev 0.00 0.61 0.00 1 0.00 0.00 Image::Image(Image const&)
A second run of the program, with me enlarging the image, rotating, translating, and negating the image resulted in a time of:
real 1m0.968s user 0m0.295s sys 0m0.297s
And a Flat profile of:
% cumulative self self total time seconds seconds calls ms/call ms/call name 33.37 0.14 0.14 6 23.36 23.36 Image::operator=(Image const&) 26.22 0.25 0.11 5 22.02 22.02 Image::Image(int, int, int) 14.30 0.31 0.06 writeImage(char*, Image&) 14.30 0.37 0.06 Image::rotateImage(int, Image&) 7.15 0.40 0.03 Image::enlargeImage(int, Image&) 2.38 0.41 0.01 Image::reflectImage(bool, Image&) 2.38 0.42 0.01 Image::translateImage(int, Image&) 0.00 0.42 0.00 6 0.00 0.00 Image::~Image() 0.00 0.42 0.00 1 0.00 0.00 _GLOBAL__sub_I__ZN5ImageC2Ev 0.00 0.42 0.00 1 0.00 0.00 Image::Image(Image const&)
Conclusion:
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