What's this sorting algorithm called?

Question

I am thinking about a non-comparison sorting algorithm and I think I've found one myself.

Input: A[0...n] ranged from 0...n //ideally, I think it can be expanded to more general case later

Non-comparison-sort(A,n):
let B = [0...n] = [0]
for i in A:
    B[A[i]]=i

After this algorithm,each element in array B will have a reference to array A and say if we want to access A[k] whose value is m, we can use A[B[m]]

I am sure I am not the first one come across this idea, So my question is what is this algorithm called?

Thanks in advance.

O(n) If memory access order was not important, this could be awesome for parallel computing on gaming GPUs — huseyin tugrul buyukisik
– huseyin tugrul buyukisik, Commented Sep 14, 2014 at 16:35

ehudt · Accepted Answer · 2013-04-04 10:56:03Z

Actually, your algorithm is not a sorting algorithm. It's an algorithm to calculate the inverse of a permutation on 0..n. In other words, it will tell you how to rearrange A in order to have all the numbers in place.

Why isn't it a sorting algorithm? If A contains all numbers in range 0..n, then the sorted array will always be B = [0, 1, 2, ..., n]. On the other hand, if A has duplicates, then this algorithm won't work. I think what you're looking to do is counting sort. This algorithm is suitable for the case where A is an array of size k, and contains numbers in the range 0..n. The algorithm has an array B of size n+1 and it counts how many time each number appears while iterating once over A.

An example for counting sort (in your pseudo-code syntax):

Counting-sort(A, n):
  let B = [0...n] = [0]
  for x in A:
    B[x] = B[x] + 1
  let C = [] // an empty list
  for i in 0...n:
    for j in 0...B[i]: // add each number 0..n the number of times it appeared in A
      C.append(i)
  return C

doptimusprime · Accepted Answer · 2013-04-04 10:36:16Z

0

After reading bucket sort here, it looks like bucket sort where the size of bucket is 1.

In Bucket sort, after putting the element in buckets, each bucket is made sorted.

However, in your case, since bucket size is 1, this step is not required. Merging the bucket is also not required since bucket size is 1 and is already merged in the array.

answered Apr 4, 2013 at 10:36

doptimusprime

9,4416 gold badges58 silver badges94 bronze badges

Comments

SmacL · Accepted Answer · 2013-04-04 10:47:58Z

0

I think you've got a pigeon hole sort there

answered Apr 4, 2013 at 10:47

SmacL

23k15 gold badges105 silver badges153 bronze badges

Collectives™ on Stack Overflow

What's this sorting algorithm called?

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related