#include #include #include #include const int ntpb = 512; //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; } } void check(int *arr, int *countArray, int size) { int counter = 0; int check[size] = {0}; for (int i = 0; i < size; i++) { check[arr[i]]++; } //Compare all the values to see if none were overriden for (int i = 0; i < size; i++) { if (check[i] != countArray[i]) { counter++; } } std::cout << counter << std::endl; } __global__ void Sort(int *arr, int size) { for (int i = threadIdx.x; 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; } } //Performs Insertion Sort on the array passed through parameter void insertionSort(int *arr, int size) { int *d_a = nullptr; cudaMalloc((void **)&d_a, size * sizeof(int)); cudaMemcpy(d_a, arr, size * sizeof(int), cudaMemcpyHostToDevice); // launch a grid of 1 block of n threads Sort<<<(size + ntpb) / ntpb, ntpb>>>(d_a, size); cudaDeviceSynchronize(); // copy from device to host memory cudaMemcpy(arr, d_a, size * sizeof(int), cudaMemcpyDeviceToHost) cudaFree(d_a); cudaDeviceReset(); } 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 *insertionArray = new int[n]; int *countArray = new int[n]; //Fill the array with randomly generated numbers fillArray(insertionArray, n); for (int i = 0; i < n; i++) { countArray[i] = 0; } //Kind of like hashtables, we increase the number of values found by 1 for (int i = 0; i < n; i++) { countArray[insertionArray[i]]++; } //Call the sorting algorithms 1 by 1 with their respecive array insertionSort(insertionArray, n); //check(insertionArray, n); std::cout << "\n\n================================================" << std::endl; std::cout << "\n\nSort is complete for N value of = " << n << std::endl; std::cout << "Errors found: "; check(insertionArray, countArray, n); std::cout << "\n\n================================================" << std::endl; //Deallocate the arrays delete[] insertionArray; delete[] countArray; return 0; }