Как называется этот алгоритм сортировки?

Question

Я думаю о некорректном алгоритме сортировки, и я думаю, что нашел его сам.

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 

После этого алгоритма, каждый элемент массива B будет иметь ссылку на массив А и сказать, если мы хотим получить доступ [к], значение которого м, мы можем использовать A [B [м]]

Уверен, что я не первый, натолкнулся на эту идею, так что мой вопрос в том, что называется этим алгоритмом?

Заранее спасибо.

Answer 1

После прочтения ведра рода here, это выглядит как ведро рода, где размер ковша 1.

В Bucket роде, после ввода элемента в ковшах, каждый ковш производятся отсортирован.

Однако, в вашем случае, так как размер ковша равен 1, этот шаг не требуется. Слияние ведра также не требуется, так как размер ковша равен 1 и уже объединен в массив.

Answer 2

На самом деле, ваш алгоритм не алгоритм сортировки. Это алгоритм для calculate the inverse of a permutation на 0..n. Другими словами, он расскажет вам, как изменить А, чтобы иметь все номера на месте.

Почему это не алгоритм сортировки? Если A содержит все числа в диапазоне 0..n, то отсортированный массив всегда будет B = [0, 1, 2, ..., n]. С другой стороны, если A имеет дубликаты, то этот алгоритм не будет работать. Я думаю, что вы хотите сделать это counting sort. Этот алгоритм подходит для случая, когда A представляет собой массив размером k и содержит номера в диапазоне 0..n. Алгоритм имеет массив B размера n+1 и подсчитывает, сколько раз появляется каждое число в то время как итерация раза над А.

примером для подсчета сортировки (в вашем синтаксисе псевдо-код):

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 

Answer 3

I думаю, что у вас есть pigeon hole sort