Algorithm help

Larry_o_C

Hi everybody,
My assignment (yes it's an assignment!) is driving me insane. Using C, the object is to define an array of integers then sort the array from least to most. Now I can find the minimum no bother but every other approach I use won't work.

#include<stdio.h>

#define N 5    // size of array

int main(int argc, char *arcv[])
{
	int minloc =0, currloc = 0, i, j, k;
	int b[N];
	int a[N];

	// array values
	b[0] = 5; b[1] = 4; b[2] = 3; b[3] = 2; b[4] = 1;




	for (j=0;j<N;j++)
	{
		for(i=0;i<N;i++)
		{	
				if( b[i] < b[currloc] )
				{
					currloc = i;
				}	
		}

		minloc = currloc;
		a[j] = b[minloc];

	}

The "new" array is merely populated with the value of the minimum of the first one. I'm not looking for an automatic fix, just a pointer in the right direction. I know it's something to do with those for loops.

Thanks

EL_Loco

if one element is less than the other you should try swapping their locations in the array, that way you move them closer to their correct position in the array.

There is a term for it but you asked for help with your own code, and not a served up solution, which I would be giving you should "the term" be mentioned.

you can do this with 1 array, but if you need the original array, copy all the elements to the 2nd array and try the swapping method on it. that way you'll have your first array, unsorted, and your second array, the result of your sort.

democrates

Wikipedia is your friend
http://en.wikipedia.org/wiki/Bubble_sort

EL_Loco

:-p damn it, that's "the term".

carveone

Larry_o_C wrote:

Hi everybody,
My assignment (yes it's an assignment!) is driving me insane. Using C, the object is to define an array of integers then sort the array from least to

I'm just happy to see people still learning C! But that code is a bit mad. What you are doing is scanning b to find the smallest value and then putting that in 'a'. Takes a bit of reading to figure that too.

If you want to do it that way then you have to find the smallest value that is still greater than the last smallest value you put in a[j]! Have a think about it. A cheat would be to mangle b[minloc] in some way by making it very big :-)

There's nothing particularly wrong with what you are doing, but it needs some more thinking about.

Larry_o_C

Cheers lads, I got it going!

carveone wrote:

I'm just happy to see people still learning C! But that code is a bit mad. What you are doing is scanning b to find the smallest value and then putting that in 'a'. Takes a bit of reading to figure that too.

If you want to do it that way then you have to find the smallest value that is still greater than the last smallest value you put in a[j]! Have a think about it. A cheat would be to mangle b[minloc] in some way by making it very big :-)

There's nothing particularly wrong with what you are doing, but it needs some more thinking about.

I know that's waht it was doing but I had a lot of different versions and well just posted the first attempt I made at it. You might cry at some of the other attempts!

carveone

Larry_o_C wrote:

Cheers lads, I got it going!

I know that's waht it was doing but I had a lot of different versions and well just posted the first attempt I made at it. You might cry at some of the other attempts!

Good job!

A lot of sorting algorithms aren't particularly obvious at first go. Which is why they put them in books. One tends to get caught by edge conditions too. For example in your case, what happens if you try and sort 5,4,1,1,1. This tends to be less of an issue in the case where you sort within the array, rather than copying it out. Then you can do stuff like:

for (k=0; k<N; k++)
for (i=k+1; i<N; i++)
if (array[k] > array)
{
temp = array[k];
array[k] = array;
array = temp;
}

(Man, I hope that's right now!)

Obviously it's more efficient to go from N to 0 rather than the other way around but still works...

Personally, I try not to use j as a variable. It looks exactly like i at 9pm

Cheers,

Conor.

Tobias Greeshman

democrates wrote:

Wikipedia is your friend
http://en.wikipedia.org/wiki/Bubble_sort

While the bubble sort is easy to think of in terms of getting your head around the algorithm. It's incredibly inefficent. For small lists of integers its better to use the "Selection Sort", it works simple really. Find the smallest number, swap the number at 1st pos with that, find the next smallest and place it at the 2nd index, and so on until theres no more integers left to sort.

http://en.wikipedia.org/wiki/Selection_sort