CODEWITHSUNDEEP
algorithmsorting
Bob Fang
Bob Fang

Reputation: 7381

What's this sorting algorithm called?

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.

Upvotes: 0

Views: 170

Answers (3)

ehudt
ehudt

Reputation: 810

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

Upvotes: 1

SmacL
SmacL

Reputation: 22922

I think you've got a pigeon hole sort there

Upvotes: 0

doptimusprime
doptimusprime

Reputation: 9395

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.

Upvotes: 0

Related Questions