Logic Challenge!

[GoldenMouse]

Using pseudo-code (computer instructions written in plain english) outline the steps to take an array of variable size and order the contents from highest to lowest.

 

[GoldenMouse]

Really, this is just a thinly veiled attempt to get some help.

 

[Bot_40]

Heh, it's a large research area...efficient sorting algorithms. If you are looking for simplicity rather than speed then bubble sort will prolly do the job.
You basically go up and down the array over and over comparing each pair of items, if they are the wrong way around then swap them, otherwise skip over. Eventually the list will be sorted. You know you are finished when you do an entire pass without making any swaps.
It's pitifully slow when you have to sort many items (proportional to the square of the nubmer of items in the array), but prolly the easiest algorithm to code.

Another easy one is selection sort. Simply keep scanning through the array and each time find the next smallest (or largest) item and move it to the back (or front depending which way you want it sorted). Again it's rather slow if you have many items (again, square of the number of items in the array but slightly faster than bubble sort iirc)

The faster algorithms generally are quite a lot harder to understand (and I am crap at explaining stuff so I won't even try at this point). Shellsort and quicksort are 2 of the fastest but quite impossible for me to explain (I never actually really got my head around quicksort). Have a look on google, there's absolutely tons of stuff on this around and I actually find it quite interesting. It's one of those things which seems like it should be rather easy to do for a human, but if you are a computer that can only compare 2 items at a time it's a hell of a lot harder.

 

[GoldenMouse]

Heh, thanks. I'm just starting to learn code. i.e. I toyed with Basica in elementary, then had nothing whatsoever to do with any code until this quarter, when I took a class on VB and have been independently going through a book on C. I plan on learning more advanced stuff once I get through this intro material. Long story short, I'm a noob to it right now. Now, I was playing risk one or two nights ago and thought that it'd be rather easy to code, once I picked up the necessary skills. In fact, I could probably write the function to handle battles.... So I'm now exactly where I want to be, stumbling on stuff that I'd never have stumbled upon without doing a project of sorts.

So this is what I found. I'm having a hard time breaking it down, though it uses no unfamiliar functions or syntax.

void insertionSort(int numbers[], int array_size)
{
int i, j, index;

for (i=1; i < array_size; i++)
{
index = numbers;
j = i;
while ((j > 0) && (numbers[j-1] > index))
{
numbers[j] = numbers[j-1];
j = j - 1;
}
numbers[j] = index;
}
}

 

[bobtheking]

what language are you using? if you are doing this as part of another project, you should probably use the ones that come with the language (they will invariably be better and faster than anything almost all programmers could write in a reasonable amount of time)

in C there is quicksort, C++ has a bunch of ways (check out the algorithm header), .Net languages some of the collections have a Sort method.

if you are doing it for learning, i would start with a bubble sort as bot_40 described. quicksort actually isn't too hard to implement, the basic idea is actually really simple. http://en.wikipedia.org/wiki/Quicksort is a really good article on it, including pseudocode and actual implementations in quite a few languages.

 

[GoldenMouse]

Very nice.

I have a headache.

 

[GoldenMouse]

Ok, I have the C source for quicksort. I'm going to try to go through and comment it. See how my comments compare to how you understand things to be. For the sake of brevity, we'll assume the swap function to be self-explanatory.

void sort(int arr[], int beg, int end)
{
if (end > beg + 1)
{
int piv = arr[beg], L = beg + 1, r = end;
while (L<R)
{
if (arr[L] <= piv)
L++;
else
swap(&arr[L], &arr[--r]);
}
swap(&arr[--L], &arr[beg]);
sort(arr, beg, L);
sort(arr, r, end);
}
}

Line 1: Accepts arguments where arr is the array to be sorted, beg is the beginning of the segment to be sorted, and end is the end of the segment to be sorted.
Line 3: Checks size of segment to be sorted to see if it has more than two values. More than two values, sort the segment. Otherwise, consider them sorted and stop the recursion.
Line 5: Initializes working variables where piv is the pivot value, L is the current item being compared, and r is the end of the working set. The pivot takes the value of the first cell to be sorted, which is random for all intents and purposes.
Line 6: Loop until working set has been sorted.
Lines 8-11: If the value of the cell in L position is less than or equal to the pivot, do nothing and move to the next cell. Otherwise, take that value and move it to the end of the set, decreasing the upperboundary of the working set by one. This segregates values in the segment into ones greater than the pivot and less than the pivot. Note that those two subsets are disordered.
Line 13: Swaps the values of the cell right before the end of the working set and the cell at the beginning of the segment. (Why?)
Line 14: Repeat this process for the smaller subset.
Line 15: Repeat this process for the larger subset.

 

[Twrecks]

new[]=order[array[max-min]]

Of course thi doesn't do squat unless you make your own operands