Linear Sorting Algorithm

[paktree]

So I have the following idea for a long time, can anyone tell me what kind of algorithm is this? Or is this consider to be an algorithm?

Let's assume:

Unlimited memory

Code:

sort()
{
  int memory[1000];
  int data[11] = {21, 20, 38, 10, 40, 299, 399, 999, 384, 394, 273};

  memset(memory, -1, 1000*sizeof(int));

  int i=0;
  for (i=0; i<11; i++)
  {
    memory[data] = data;
  }

  int j=0;
  for (i=0; i<1000; i++)
  {
    if (memory != -1)
    {
      memory[j++] = i;
    }
  }
}

Isn't this O(n)?

[MikeMruzik]

Hey there, check out this page: http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

There, they outline all of the common sorting methods, highly recommended reading.

As for your code there, I'm not exactly sure what you're trying to do .. You put all the members of data[11] into memory[data] and make all other members of memory -1.. not really any sorting whatsoever. :( another thing, if any members of data[] are <-1 or >999, the program will crash.. check out that site for practical sorting algorithms :) the bubble sort is probably the easiest to understand and easiest to code... check it out. :)

[blacklee]

So I have the following idea for a long time, can anyone tell me what kind of algorithm is this? Or is this consider to be an algorithm?

Yes, it's hashing .

Isn't this O(n)?

Yes! Cool, isn't it?
I wrote a progaram for 240 using this same method, although I had no idea it was called hashing until I took 340.

[William Grim]

Isn't this O(n)?

Yes! Cool, isn't it?

No, it's actually an exponential algorithm whose worst-case run time is determined by the maximum power-of-10-number in the data set.  In this case, the largest number is 999.  So, 999+1 words are needed to store every possible number between 0 and 999 inclusive.  So his algorithm is running at 10**3 right now.  If the highest number was 9999, you'd have to check 10**4, etc.

[blacklee]

Yes, Mike is right of course. It takes O(n) to hash items into an array in sorted order, but you'd have bunch of empty spaces. Last 3 line of your code is not O(n).

[R. Andrew Lamonica]

paktree,
I applaud your attempt.  Do not let the naysayers get you down.  It is easy to poke holes in someone else’s idea, while it is hard to be brave enough to post an idea for public scrutiny in the first place.

As the previous posts mentioned, your implementation of this sort leaves a great deal to be desired.  However, you did hit upon a few important computer science concepts with this post.

1) Bucket sort (which is what you made a stab at implementing) is a pretty fast sort because it is not a traditional comparison sort and makes use of memory instead.

2) The time-complexity/memory-use tradeoff in many common computer science problems is an important factor in implementations.  For example, you can find all the prime numbers less than X without doing any factoring provided that you have X-bits of fast memory at your disposal.  Unfortunately, this is not practical for big primes because computer memory is not really that fast if you use a lot of it.  There are, however, many problems that are slow unless you make use of a memory cache for partial solutions.  This technique is often used in dynamic programming.

For some practice using dynamic programming, try solving this ACM problem using the â€Ã...“Dynamic programmingâ€Ã, algorithm listed here.  My solution was less than 100 lines long and mirrored the Wikipeida article’s suggestion closely.  Currently, it is the 7th fastest solution to this problem that has been posted to the ACM site.

R. Andrew Lamonica

[William Grim]

The bucket sort works nicely only when the range of possible input is small.  When the range gets large, you head towards the exponential runtime as discussed earlier.  The only way to mitigate this problem is to have larger and larger buckets which then means it probably makes more sense to just go with a standard comparison sort at that point.

Having said that, to be able to determine the possible range of incoming input is probably easy most of the time.  So, you could just check the range before having your code deciding to use bucket sort or some other algorithm.

[paktree]

Thanks for all the replys.

Yes, I realized that this algorithm is bucket sort (bin sort). And I saw some people have put some work to generalize that algorithm to handle all cases.

I am not an expert on algorithm but trying to get an answer for a long time question I got.

When computation power goes further and further, I am pretty sure O(n) sorting algorithm is coming in place shortly. :)