Playing with pointers and arrays

[jimtuv]

I am building up to searching and sorting so I thought a little practice with swapping numbers would be relevant. I started with the most simple of problems swapping two integer variables then decided to have some fun and see if I could apply that too an array. So I set one up and flipped it backward.

I know it's not all that impressive but hey I am just starting off ;P

Here is my code

#include <stdio.h>

void SwapNumb( int* a, int* b);
void PrintArray(int size, int* ptr);

int main(void){
	
	int fnumber, snumber, i ;
	int* pf, ps;	
	int anumbers[] = {0,1,2,3,4,5,6,7,8,9};
	
	pf = &fnumber;
	ps = &snumber;
	
	*pf = 5;
	*ps = 6;
	
	printf("\n\n");
	printf("Here are numbers %d and %d \n", fnumber,snumber);
	SwapNumb(pf,ps);
	printf("Here they are after the swap %d and %d \n\n", fnumber,snumber);	 	
	
	printf("Here is an array\n");
	PrintArray(10,anumbers);
	printf("\n\n");	 
	 
	 pf = anumbers;
	 ps = anumbers + 9;
	 
	 for ( i = 0 ; i < 5 ; i++){				 
		 SwapNumb(pf,ps);
		 pf ++;					
		 ps --;
	 }	 
	 
	 printf("Here is an array backwards\n");
	 PrintArray(10,anumbers);
	 printf("\n\n");			
	
	return 0;
}
/*---------------------------------------------------------------------------
* SwapNumb
* parameters:
* 	int* a:      is a pointer to the location of the
			first number to be swapped
*	int* b:      is a pointer to the location of the 
			second number to be swapped
* prints:           nothing
* returns;         nothing
*------------------------------------------------------------------------------*/
void SwapNumb( int* a,  int* b){
	
	int holder;
	
	holder = *a;
	*a = *b;
	*b = holder;	
}
/*-------------------------------------------------------------------------------
* PrintArray
* parameters:
*	int size:     is the size of the array to print
*	int* ptr      is a pointer to the array to print
* prints:             an array
* returns:          nothing
*------------------------------------------------------------------------------*/
void PrintArray(int size, int* ptr){
	
	int i;	
	
	for ( i = 0 ; i < size ; i++ ){
		printf("%d,", *(ptr + i));
	}
}

I am sure some of you are wondering why I am posting so frequently. Well that is because I am learning on my own. I don't have the feed back that you would get studying this at school and it's been super valuable to hear the opinions of those who know what they are doing. So please be patient with me.

[Salem]

Looks good

[MK27]

I am sure some of you are wondering why I am posting so frequently. Well that is because I am learning on my own. I don't have the feed back that you would get studying this at school

Post as much as you want. Worst case scenario: everyone ignores you

I was brand new to C when I started here 2 years ago, and I'd bet I've learned more about C programming during that time than I would have following a curriculum somewhere.

One major point which should result in a compiler error:

	int* pf, ps;

These are not both int pointers! That would be:

	int *pf, *ps;

What you have may work on 32 bit systems where an int is the same size as a pointer. But an error should still occur here:

	*ps = 6;

Since an int cannot be dereferenced.

Another point, which is not really a criticism, just a tip: you actually don't need the pointers, you can use "address of" all the time:*

int main(void){
	
	int fnumber, snumber, i ;
	int anumbers[] = {0,1,2,3,4,5,6,7,8,9};
	
	printf("\n\n");
	printf("Here are numbers %d and %d \n", fnumber,snumber);
	SwapNumb(&fnumber,&snumber);
	printf("Here they are after the swap %d and %d \n\n", fnumber,snumber);	 	
	
	printf("Here is an array\n");
	PrintArray(10,anumbers);
	printf("\n\n");	 
	 
	 for ( i = 0 ; i < 5 ; i++){				 
		 SwapNumb(&anumbers[i],&anumbers[9-i]);
	 }	 
	 
	 printf("Here is an array backwards\n");
	 PrintArray(10,anumbers);
	 printf("\n\n");			
	
	return 0;
}

Try it.


* it's the concept of "pointing" and "pointers" that's key.

[Babkockdood]

That looks very confusing.

[jimtuv]

One major point which should result in a compiler error:

	int* pf, ps;

These are not both int pointers! That would be:

	int *pf, *ps;

What you have may work on 32 bit systems where an int is the same size as a pointer. But an error should still occur here:

	*ps = 6;

Since an int cannot be dereferenced.


[/code]

I did this one with a text editor and used the command line to compile it with gcc. I have to remember not to do that again! I put it into code::blocks and sure enough it showed the errors.

here is the fixed code

#include <stdio.h>

void SwapNumb( int* a, int* b);
void PrintArray(int size, int* ptr);

int main(void){

	int fnumber, snumber, i ;	
	int anumbers[] = {0,1,2,3,4,5,6,7,8,9};	

        fnumber = 5;
        snumber = 6;

	printf("\n\n");
	printf("Here are numbers %d and %d \n", fnumber,snumber);
	SwapNumb(&fnumber,&snumber);
	printf("Here they are after the swap %d and %d \n\n", fnumber,snumber);

	printf("Here is an array\n");
	PrintArray(10,anumbers);
	printf("\n\n");	

	for ( i = 0 ; i < 5 ; i++){
		 SwapNumb(&anumbers[i],&anumbers[9-i]);
        }

	printf("Here is an array backwards\n");
	PrintArray(10,anumbers);
	printf("\n\n");

	return 0;
}
/*---------------------------------------------------------------------------
* SwapNumb
* parameters:
* 	int* a:      is a pointer to the location of the
			first number to be swapped
*	int* b:      is a pointer to the location of the
			second number to be swapped
* prints:           nothing
* returns;         nothing
*------------------------------------------------------------------------------*/
void SwapNumb( int* a,  int* b){

	int holder;

	holder = *a;
	*a = *b;
	*b = holder;
}
/*-------------------------------------------------------------------------------
* PrintArray
* parameters:
*	int size:     is the size of the array to print
*	int* ptr      is a pointer to the array to print
* prints:             an array
* returns:          nothing
*------------------------------------------------------------------------------*/
void PrintArray(int size, int* ptr){

	int i;

	for ( i = 0 ; i < size ; i++ ){
		printf("%d,", *(ptr + i));
	}
}

It is much cleaner without the pointers. I am beginning now to make a search algorithm.

It seems the most logical way would be to learn to sort first then after the data is in order I could just start in the center of the array and then decide if the number I am looking for is greater or less then the one at the that location if it is less I can would only need to search the lower part from then on if greater then only search the upper part.

next loop would jump to the center of the remaining elements of the array and again look to see if the number there were greater then or less then.

shouldn't need many iterations to find a number even in a huge array.

So That is what the swap was all about I need to sort first. I will need a pointer for the current lowest number and one for the bottom position in the array at element [0] the first go round and would move up by one after each swap. by finding the lowest number and swapping with the bottom number it should eventually sort the whole array.

So I should do a simple loop looking up the array comparing the number at the current lowest number point to the next and if its lower then move the current lowest number pointer to this point in the array else keep going moving the array by one element comparing if it is less each time. When it hits the last number in the array the current lowest pointer should be at the total lowest number and I can swap that with the bottom number in the array.

I will have to do a flow chart I think to nail it down but this approach seems reasonable to me.

[Bayint Naung]

Where's searching??!

[LordPc]

just a little thing that might help you out

im sure you've learnt by now about magic numbers. well here is something you can do to help you get the length of an array by magic

	int anumbers[] = {0,1,2,3,4,5,6,7,8,9};
	int arrayLength = sizeof(anumbers)/sizeof(int);
	PrintArray(arrayLength, anumbers);

arrayLength in this example is 10. the cool thing about using sizeof() is that you can do this

	int anumbers[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
	int arrayLength = sizeof(anumbers)/sizeof(int);
	PrintArray(arrayLength, anumbers);

so you can make the array bigger and the arrayLength variable will calculate itself for you

[jimtuv]

I am beginning now to make a search algorithm.

It seems the most logical way would be to learn to sort first then after the data is in order I could just start in the center of the array and then decide if the number I am looking for is greater or less then the one at the that location if it is less I can would only need to search the lower part from then on if greater then only search the upper part.

next loop would jump to the center of the remaining elements of the array and again look to see if the number there were greater then or less then.

shouldn't need many iterations to find a number even in a huge array.

So That is what the swap was all about I need to sort first. I will need a pointer for the current lowest number and one for the bottom position in the array at element [0] the first go round and would move up by one after each swap. by finding the lowest number and swapping with the bottom number it should eventually sort the whole array.

So I should do a simple loop looking up the array comparing the number at the current lowest number point to the next and if its lower then move the current lowest number pointer to this point in the array else keep going moving the array by one element comparing if it is less each time. When it hits the last number in the array the current lowest pointer should be at the total lowest number and I can swap that with the bottom number in the array.

I will have to do a flow chart I think to nail it down but this approach seems reasonable to me.

There is the searching
say I were looking for 27 in this array

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30
                                  ^
                               higher

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30
.                                                      ^
.                                                   higher

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30
.                                                                    ^
.                                                                 bingo!

Thanks LordPc I will certainly use that it is so handy!!!!

[Bayint Naung]

It's better to use sizeof(anumbers)/ sizeof(anumbers[0]) ;
This will work even if you change the type of anumbers to array of double or array of struct.

#define NELEM(array)        ( sizeof(array)/sizeof(array[0]) )

[MK27]

by finding the lowest number and swapping with the bottom number it should eventually sort the whole array.

So I should do a simple loop looking up the array comparing the number at the current lowest number point to the next and if its lower then move the current lowest number pointer to this point in the array else keep going moving the array by one element comparing if it is less each time. When it hits the last number in the array the current lowest pointer should be at the total lowest number and I can swap that with the bottom number in the array.

What you are describing is called selection sort. The first time I had to sort something, I did what was intuitively obvious to me, and that turned out to be the "modified bubble sort". Anyway, probably a good idea to go ahead with what makes intuitive sense to you and then afterward you can consider other sorting algorithms. It is sort of (pun) amazing how many ways people have come up with to sort arrays. Some of them are almost diabolically clever.

[Elysia]

Oh and your search algorithm is called binary search
Only works on sorted arrays, but when it does, it works O(log n) time. Blazing speed.

[LordPc]

dont ruin it for him.

he's in a very unique position where the terms selection and bubble sort dont mean anything.

let him explore, see what he comes up with.

[Elysia]

I find it interesting to know when I've actually thought up an algorithm in my head that's actually a known standard algorithm. I'm sure it applies to others, too.

[jimtuv]

It's better to use sizeof(anumbers)/ sizeof(anumbers[0]) ;
This will work even if you change the type of anumbers to array of double or array of struct.

#define NELEM(array)        ( sizeof(array)/sizeof(array[0]) )

Yep I can see how thats better. I have been thinking about this and it only makes sense because an array's size in bytes would be the number of elements * size of the type. So it follows logically that the number of elements can be derived from the opposite operation.

What you are describing is called selection sort. The first time I had to sort something, I did what was intuitively obvious to me, and that turned out to be the "modified bubble sort". Anyway, probably a good idea to go ahead with what makes intuitive sense to you and then afterward you can consider other sorting algorithms. It is sort of (pun) amazing how many ways people have come up with to sort arrays. Some of them are almost diabolically clever.

Trust me this sorting algarythm is not intuitive just the first idea. It seems way to slow right now. I really haven't given the sort that much thought yet. I had been concentrating on the search.

What I did is to go into Open Office Calc and put a bunch of random numbers down the A column then asked myself how would I find a number in that array. The obvious answer was just to start at the first cell and scan down but I realized right away it works fine for small arrays but giant ones would take forever. That is when I realized if I sorted the column that finding the number would be that much faster because I could use the <> test and limit the search.

I probably should have Googled "search" and "sort" first but I didn't want to spoil the fun of trying to figure it out on my own.

Oh and your search algorithm is called binary search
Only works on sorted arrays, but when it does, it works O(log n) time. Blazing speed.

didn't realized the name of it but did quickly realize the need to sort the data. I have to come up with a better sort. I will give it some more thought before giving in and searching on-line

I have been thinking of using something similar with the sort. breaking the array up into sections of greater then and less then and sorting from there. To do that I think would require to set a couple points in the array to sort between sorting from lowest to highest in a block between the two points. then using that lower point to swing down and do a sort again this time only in the low section of the block sorting lowest to highest. It should end up making smaller and smaller blocks of greater and less then and eventually sort everything.

Not sure that's a good idea or how efficient it would be. I am just in the beginning stage of putting it into an algorithm.

[Elysia]

I have been thinking of using something similar with the sort. breaking the array up into sections of greater then and less then and sorting from there. To do that I think would require to set a couple points in the array to sort between sorting from lowest to highest in a block between the two points. then using that lower point to swing down and do a sort again this time only in the low section of the block sorting lowest to highest. It should end up making smaller and smaller blocks of greater and less then and eventually sort everything.

Now you're on a roll!
There are two known algorithms that sort in O(n log n) time that work like this. They're called Quicksort and Mergesort.
If you can get that working (can be difficult), then you've invented a great algorithm without looking up any known ones!
I think you've got a knack for logic. You could probably become a great programmer after some experience.