[List] The Best Algorithms

[TheZsterBunny]

It's contest season ladies and gents. you know what that means.

so, i thought, maybe it'd be a good idea to put together a list of powerful algorithms that would be useful for contest questions.

no junk like "the color at this point" but useful stuff, like information handling & manipulation.

I'll go first:
[Method: Merge Sort, Language: Java]
This algorithm uses the divide and conquer technique to sort information. it breaks down a list into elements of one, compares them, and builds up from there. Solves in nlogn time.

code:

public static void mergeSort (int s[], int lo, int hi) {                 if (lo >= hi) {                         return;                 }                 int mid = (lo+hi)/2;                 mergeSort (s,lo,mid);                 mergeSort (s,mid+1,hi);                 int lo_end = mid;                 int hi_start = mid+1;                 while ((lo<=lo_end) && (hi_start <= hi)) {                         if (s[lo] < s[hi_start]) {                                 lo++;                         } else {                                 int t = s[hi_start];                                 for (int i = hi_start -1; i>= lo;i--) {                                        s[i+1] = s[i];                                 }                                 s[lo] = t;                                 lo++;                                 lo_end++;                                 hi_start++;                         }                 }         }

-Z

[bugzpodder]

I'd be surprised if you see a merge sort question in a contest situation... (well technically there would be modified merge sort that finds number of inversions, but those are exceedingly rare)

I am actually wanting to establish a nice code base contest algorithms... You might be surprised how hard it is to find existing code on the net...

I may just clean up sorce codes and post it up in some respect. The algorithms are just too numerious to list. But I want to start on 2D Computational Geometry since it is the most useful in terms of prewritten code. The idea is to keep the implementation short, efficient, robust.

What I have in mind: segment intersection, convex hull, circumcenter, delaunay triangulation/voronoi diagram (I have so far failed to find a short sub n^2 implementation of this)

[MysticVegeta]

What? Why cant we just use Arrays.sort(); in java? Whats the deal with using Merge sort? Faster?

[codemage]

If raw speed is essential, memorize shellsort or heapsorting algorithms. Don't limit yourself to slow, old merge.

(1/2 kidding here).

[JackTruong]

Arrays.sort uses the Bubble Sort algorithm, which is the slowest of the O(n²) algorithms.

Insertion is probably the best (in terms of speed and complexity) of the O(n²) sorting algorithms.

[[Gandalf]]

No... not quite...

java.sun.com wrote:

public static void sort(int[] a)

Sorts the specified array of ints into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

Parameters:
a - the array to be sorted.

[JackTruong]

Oh.. never knew that.

My mistake..

[rizzix]

As for algorithms, well i know a site that is basically a repository for general, resuable source code: http://www.koders.com/

[bugzpodder]

holy fuck that site looks awsome

[md]

taking other people's code isn't nessessarily good. If you don't know how it works then you're probably going to make mistakes.

It is rather neat though

[Martin]

The idea being not to reinvent the wheel I think.

[bugzpodder]

Cornflake wrote:

taking other people's code isn't nessessarily good. If you don't know how it works then you're probably going to make mistakes. It is rather neat though

So write everything from scratch in asembly? If you have ever called an API or another library (like Java's) or even IO routines like cin/cout, you are effectively using other's code.

[MysticVegeta]

I am sure Cornflake meant creating your own code as in routines/methods and not the assembly part lol

[codemage]

bugzpodder wrote:

So write everything from scratch in asembly? If you have ever called an API or another library (like Java's) or even IO routines like cin/cout, you are effectively using other's code.

Real programmers don't consider assembly to be scratch. Assembly is a clear cut framework of syntax and commands designed to make low-level programming easy for newbs and wussies.

Real programmers don't even program in machine code. They have an array of bared wires that they connect in proper sequence with a paperclip.

[md]

I was thinking more like if you always copy someone elses code and try and peice bits of other peoples code together and call it your own you won't know how it works and most likely it won't work very well.

Standard libraries are a bit different in that they are standard, and well documented. Reinventing them is rather pointless since they generally do exactly what you need, and are documented enough so that you know what'll happen when you call a certain peice of code. However; re-writing bits and peices just to see how it might be done is always fun