C++ :: Timing Function - Sort Dynamic Array With N Elements
Apr 11, 2014
I'm writing a program that will implement BubbleSort and MergeSort and time them as they sort a dynamic array with N elements. These are the instructions on what my main.cpp file should do.
main.cpp
Include all needed libraries for timing and random number generation while the number of element, N, is less than 100001 repeat the following.
create an array with N (initially 10) random elements
sort the same array with Bubble and Merge sort
time how long it takes each algorithm in microseconds (see example below)
Increase N by a factor of 10 (N *= 10)
Hint: you may want to put your merge sort object on the heap and delete it with every iteration of this loop
I have to write a function called sortMe that sorts the elements of an array in numerical order from highest to lowest values (descending order) or vice versa (ascending order).
The assignment asks to: NOT re-arrange elements in the array; instead, it uses a second array, an array of indexes for the elements in the original array and then sortMe sorts the second array based on the values in the original array. A sorted version of the original array can then be produced with these sorted indexes.
Header of the function sortMe must be as shown below:
void sortMe(int array[],int sortedIndexes [], int size, char mode)
When mode is 'a', the function sorts the array in the ascending order, and when mode is 'd', the function sorts it in the descending order.
Declare and initialize the array array.
Declare the array sortedIndexes but do not initialize it. You are going to play with the array sortedIndexes in the function sortMe.
EXAMPLE:
int array[5]={3, 5,-1,10,0}; int sortedIndexes[5]; sortMe(array,sortedIndexes, 5, 'a');
After the function call, the elements of the array sortedIndexes should be: 2,4,0,1,3.
notice that the function does not e-arrange the elements in the array.
I'm having a bit of trouble trying to delete elements in a dynamic array of objects. I tried to delete elements by shifting that particular element and the ones that follow over one element and then assigning the last one to NULL.
cin >> input; while (input != -1 || k == 7) { for(int i = 0; k < numberOfRecords; i++) { if (input == records[k].id) {
Now I have to write a function show_exam_descending(Data d, string subCode) when I call show_exam_descending(d, "ENGL_S12") the program will execute to show all the students' exam scores in ENGL_S12 in DESCENDING order...
For this to run, I have declared a struct Data:
struct Data { string subjectCode; int studentCode; double examScore; );
For the search, I have written a function before to load all the data from the document by using pointer and dynamic arrays. It works so well. What troubles me is the way to swap the elements (i.e. examScore) of different students in struct dynamic arrays. I am able to display all of them, but don't know how to swap.
So I try to sort an array with qsort and then save the new order, so this means if I have a list like:
4 3 7 2 [0] [1] [2] [3],
after sorting it becomes:
2 3 4 7 [3] [1] [0] [2] <== this is what I want to have!
Code:
void qsort_my(int *a, int l, int r, int *array_order) { int j; if( l < r ) { j = split( a, l, r, array_order); qsort_my( a, l, j-1, array_order); qsort_my( a, j+1, r, array_order);
[Code]...
But my problem is that the list gets sorted, but the indexes do strange stuff. When I run with this list:
4 8 14 1 2 1 22 12 2 14 Pos: 0 1 2 3 4 5 6 7 8 9
I get:
1 1 2 2 4 8 12 14 14 22 Pos: 1 0 1 0 0 5 7 6 5 6
And with some printfs I noticed, the first two calls of split it is fine but then strange things start to happen, what I do wrong?
Example radix sort function to sort an array of 64 bit unsigned integers. To allow for variable bin sizes, the array is scanned one time to create a matrix of 8 histograms of 256 counts each, corresponding to the number of instances of each possible 8 bit value in the 8 bytes of each integer, and the histograms are then converted into indices by summing the histograms counts. Then a radix sort is performed using the matrix of indices, post incrementing each index as it is used.
Code: typedef unsigned long long UI64; typedef unsigned long long *PUI64; PUI64 RadixSort(PUI64 pData, PUI64 pTemp, size_t count) { size_t mIndex[8][256] = {0}; /* index matrix */ PUI64 pDst, pSrc, pTmp; size_t i,j,m,n; UI64 u;
Code: Int** d = malloc( ROWS * sizeof(int*)); for (i = 0; i < ROWS; i++) d[i] = malloc(COLS * sizeof(int)); fx(d);
My question is, in a function declaration, why do I not have to specify the number of columns. How is this different than when I pass a static 2D array to a function, in which I must declare the function parameter with the number of columns.
Code: void fx(int d[][COLS]); VS. Code: void fx(int **d);
I made a resize function for my dynamic array template class that goes as follows. Note that the private member variables are T* arr, unsigned used, and unsigned cap.
template <class T> void darray<T>::resize(unsigned size) { if (size > cap) { T* temp_arr = new T[size];
[Code] ....
Whenever I use this function to increase the size of the array, it will work the first time I need to use it, but after that, Visual Studios will trigger a breakpoint at line 14, and if I continue past the breaks, I eventually get _CrtIsValidHeapPointer(pUserData) assertion failure.
I am trying to pass a dynamic array to a function which will:
- Copy the contents of the array to a temporary dynamic array - Change the array passed in to one size bigger - Copy the elements from the temp array back into the newly changed array - Insert an item into the last spot of the array
Here is my code:
#include <iostream> using namespace std ;
void make_array ( int Old [] , int & old_size , int toInsert ) ; void zero_array ( int arry [] , int arry_size ) ; void print_array ( int arry [] , int arry_size ) ;
[Code] .....
The output seems like a memory address but is just a very large number, what have I done incorrectly to cause this?
I have this code(homework) i've been working on for several days i couldn't fix this error.
Question is: to write a sort program in c . Ineed to ask user for how many numbers to be sorted(n) ask again for values. The approach of sort is this:
1- store n in temporary var (temp) 2- search for largest number in array (0 until temp-1) 3- switch the fied that store largest with field indexed by (temp-1) 4- temp-- (decrement) 5- repeat steps 2 to 4 until temp is 1
the program then prints the numbers of array on screen in one line. I also should use a function getMax(int *list , int n) that determines largest value and returns its location in that array
list : is the array n: number of elements
Code: #include<stdio.h> int getMax(int *list, int n); //definition of getMax function int main(void) { int n,i;
[Code] .....
so i tried to sort this array
Code: input 2 7 9 4 3 1 6 5 The out put should be : 9 7 6 5 4 3 2 1 instead it prints : 7 9 2 4 3 1 6
/part of main function int *A=NULL; //load from file load_from_file(A, &next); printf("next=%d ",next); getchar(); printf("A[%d]=%d ",0,A[0]);getchar();//here program crashes }
[code]....
I initialize array A with NULL in main, and I "load" it with elements from a file. The code without function is working. But when I tried to use a function as above, my array crashes!!!
I'm working on a piece of code written long time ago. Without getting in the details or too much context here, there is a function that declares an array of char of a size of 350,000 elements, in order to fill it (using a pointer) with the list of all running processes on the machine (using "ps -ejf" on a Linux box).
The size of the char array has been changed from 40,000 to 350,000 sometime along the years, probably because of a lack of space required.
What kind on data structure / storage would you use to store the running processes in order to eventually search for a value in it?
I'm still fairly new to c++ and am having trouble with dynamic arrays. My task is to create an array for test scores. The user needs to define the size of the array and then input data to later sort and calculate the average.
Below is what I have so far. I am struggling with the user input part. I receive the following errors for the data input of the individual scores:
"error C2108:subscript is not of integral type" "IntelliSense:expression must have integral or unscoped enum type"
Code :
#include<iostream> #include<iomanip> using namespace std; int main() { //user input total number of scores cout<<"Please enter the total number of test scores."<<endl<<endl;
I need to create a main function with a one dimension dynamic array with float data type. The total number of array elements must be controlled by a user input from the keyboard. Test data is three different lengths 3,6,9 of the array. The lengths have to be set up at run time from users input. I understand how to create dynamic array but not where the user inputs the length of the array. How would I implement this?
I am trying to use smart pointers to sort and re-link potentially large data elements. I have defined a class in my code for smart pointers, as listed below:
The object I'm trying to sort is a singly-linked list containing class objects with personal records (i.e., names, phone numbers, etc.). The singly-linked list class has an iterator class within it, as listed below.
The following is my function within my list class for "sorting" using the smart pointers.
template <typename T> void slist<T>::sort(){ vector< sptr<node> > Ap(N); // set up smart point array for list //slist<T>::iterator iter = begin(); node *ptrtemp = head->next;
[Code] .....
I must have a bad smart pointer assignment somewhere because this code compiles, but when I run it, std::bad_alloc happens along with a core dump. Where am I leaking memory?
I am looking at a same application in c that uses two different timing techniques. One involves the nanosleep() function which suspends thread for given nanoseconds. The other one uses a combination of gettimeofday() which returns number of microseconds since epoch as a start value. Then it uses var counter of for loop as max value. And it uses ellapsed time for each call of gettimeofday in microseconds in a do while loop to increment diff, until diff is not less than var. Why would someone choose to use this timing techinque be used instead of nanosleep?
I've written a timer function in c/c++, but it still has performance problems. how to optimize this further (atm works with delay to perform timing):
#include "headers/types.h" //Basic types! #include "headers/timers.h" //Timer support function data! #include "headers/emu/threads.h" //Thread for timer item! //Timer step in ms! Originally 100ms #define TIMER_STEP 10000
I'm writing a program in which I have to use a matrix to represent a file in code. because it's a file, the size of the matrix is undefined, and therefore the matrix has to be dynamic. I found out that my compiler doesn't like dynamic multidimensional arrays, so I was thinking of this matrix as a dynamic (monodimensional) array of other dynamic (monodimensional) arrays. My program (and thus this example) uses unsigned chars.
I have a struct called Array and I'm to create a function to create a dynamic array that's fill with randomly generated integers from 0 to 50 (inclusive) and a function to destroy the array for freeing its memory. Below the code that I have written so far.
Code:
* Struct */ typedef struct {int *pArray; //the dynamic array int length; //the size of the dynamic array}Array; /* Function to create a dynamic array */ Array *initializeArray (int length) {int i; }
