First, I am totally new to C++. I've learned to program in C, but that was long time ago. I am now more comfortable with Matlab, IDL, or python. I plan to get familiar with C++ by using it to do the assignments from the online course Algorithm 2. The first task from the course involves a sorting problem. So that's where we started.
I did not expect this to take away a whole afternoon from me. That is to say, I did not expect to learn so many stuff from this practice, it's worth to put them down.
1). before using a variable, declare it first. This is annoying after getting used to Matlab. The type of the function, and the type of parameters all have to be decided in front. I saw in the textbook that the function have to be declared before the main function so I also did this. I think it is necessary.
2). the variables that declared inside a block are local variables. This block even include a IF statement! Although I like the idea of local variable, I am constantly running out of short names like 'x', 'y', 'i', 'j', 'k'. It is so stupid that one cannot declare new variables inside an IF statement or FOR loop and use it outside. Me myself have trouble to believe in this. But when I tried to declare a new array inside an IF, it cannot be accessed outside that IF statement. I cannot declare it outside because I want to read the size from a file, and I believe it is necessary to add an IF to check that the file is actually opened. I haven't found a proper way to do this till now.
3). pointers. '&' means "the address of" and '*' means "the value this pointer points to". The '*' used differently when declaring a pointer, you do like 'int*' to say it is a pointer points to an integer. The interesting part is that when you point to an array, the pointer behaves just like the array.
For example,
int array[5] = {1, 2, 3, 4, 5};
int* pointer;
pointer = array;
Then pointer[3] = 4, just like array[3].
I use pointers as a parameter in the sub-function because I thought in this way the original values can be changed in the sub-function. I am actually not sure that this cannot be done by passing the array directly, since an array is basically a constant pointer. Need to check another time.
4). file operations are done by "fstream" package (package?). In my case of reading a '.txt' file, the 'file >>' reads one data at one time and ignores the space and enter in between.
5). quick sort. The idea is to choose a number in the array (randomly chosen is OK, I just use the rightmost value) as a pivot, and put the values that are larger than the pivot to the right side of the array, and the values that are smaller than the pivot to the left side of the array. After this, what we've done is, i) we find the correct position for the pivot, ii) we break the array into two sub-arrays, in one array all the values are smaller than pivot and in the other larger. So the next step is to repeat what has been done to till now to the sub-arrays separately till only one value left in the sub-array. The repeating part can be done by calling the quick sort recursively. It is said the expect running time is O(nlog(n)). I need to check on that.
6) code. The WLK is just a struct I created, the WLK.key value is used for sorting.
I did not expect this to take away a whole afternoon from me. That is to say, I did not expect to learn so many stuff from this practice, it's worth to put them down.
1). before using a variable, declare it first. This is annoying after getting used to Matlab. The type of the function, and the type of parameters all have to be decided in front. I saw in the textbook that the function have to be declared before the main function so I also did this. I think it is necessary.
2). the variables that declared inside a block are local variables. This block even include a IF statement! Although I like the idea of local variable, I am constantly running out of short names like 'x', 'y', 'i', 'j', 'k'. It is so stupid that one cannot declare new variables inside an IF statement or FOR loop and use it outside. Me myself have trouble to believe in this. But when I tried to declare a new array inside an IF, it cannot be accessed outside that IF statement. I cannot declare it outside because I want to read the size from a file, and I believe it is necessary to add an IF to check that the file is actually opened. I haven't found a proper way to do this till now.
3). pointers. '&' means "the address of" and '*' means "the value this pointer points to". The '*' used differently when declaring a pointer, you do like 'int*' to say it is a pointer points to an integer. The interesting part is that when you point to an array, the pointer behaves just like the array.
For example,
int array[5] = {1, 2, 3, 4, 5};
int* pointer;
pointer = array;
Then pointer[3] = 4, just like array[3].
I use pointers as a parameter in the sub-function because I thought in this way the original values can be changed in the sub-function. I am actually not sure that this cannot be done by passing the array directly, since an array is basically a constant pointer. Need to check another time.
4). file operations are done by "fstream" package (package?). In my case of reading a '.txt' file, the 'file >>' reads one data at one time and ignores the space and enter in between.
5). quick sort. The idea is to choose a number in the array (randomly chosen is OK, I just use the rightmost value) as a pivot, and put the values that are larger than the pivot to the right side of the array, and the values that are smaller than the pivot to the left side of the array. After this, what we've done is, i) we find the correct position for the pivot, ii) we break the array into two sub-arrays, in one array all the values are smaller than pivot and in the other larger. So the next step is to repeat what has been done to till now to the sub-arrays separately till only one value left in the sub-array. The repeating part can be done by calling the quick sort recursively. It is said the expect running time is O(nlog(n)). I need to check on that.
6) code. The WLK is just a struct I created, the WLK.key value is used for sorting.
没有评论:
发表评论