Алгоритм хеш-сортировки

Всегда были споры о том, как можно достичь алгоритма сортировки с линейной временной сложностью, поскольку все традиционные алгоритмы сортировки в худшем случае имеют порядок не менее O(N*log(N)) .

Причина трудности достижения линейно пропорциональной временной сложности в алгоритме сортировки заключается в том, что большинство этих традиционных алгоритмов сортировки основаны на сравнении, что в худшем случае не может обеспечить отсортированный вывод набора данных за линейное время. Чтобы решить эту проблему, появился алгоритм хэш-сортировки, который даже быстрее, чем самый быстрый традиционный алгоритм сортировки, то есть быстрая сортировка.

Предположения о хеш-сортировке:

Предположения, сделанные при реализации сортировки по хэшу:

1. Значения данных находятся в пределах известного диапазона.
2. Значения имеют числовой характер.

Работа алгоритма:

Как следует из названия, алгоритм сочетает в себе концепцию хеширования с сортировкой.

Но как можно использовать хеширование для сортировки? Ответ на этот вопрос заключается в использовании супер-хеш-функции .

The super-hash function is a composite function of 2 sub-functions: 

1. Hash function 
2. Mash function, which helps the super-hash function to allocate the data values to unique addresses (i.e. no collision happens) in a consistent way (means no scattering of the data).

Теперь эти сопоставления значений данных, полученных из суперхеш-функций, используются основными методами сортировки хэшей. Структуры данных, используемые для хранения и сортировки данных, являются матрицами. Существует несколько версий методов сортировки хешей, в основном их две:

1. Хэш-сортировка на месте . В этом методе и хранение, и сортировка значений происходят в одной и той же структуре данных.
2. Прямая хеш-сортировка . В этом методе для хранения данных используется отдельный список данных, а затем из этого списка выполняется сопоставление с многомерной структурой данных.

Суперхеш-функция:

Суперхэш-функция представляет собой комбинацию двух подфункций, называемых хеш-функцией и функцией мешанины . Эти две функции используются вместе для достижения отличия значений данных друг от друга, поскольку простая хеш-функция не может этого сделать из-за проблемы коллизии. Две подфункции работают следующим образом для достижения цели суперхеш-функции:

Рассмотрим общую форму числа: cx + r , где c — значение величины, x — основание (обычно 10), а r — полученный остаток.

• Хеш-функция: это работает с различением значений для отображения на основе остатка, т. е. оператор mod применяется к значениям данных для получения остатков, и эти остатки используются для размещения данных в определенном месте при отображении. Итак, основная хэш-функция: ( X mod N ). Но использование только этого метода может привести к конфликтам, потому что для заданного значения остатка может быть несколько значений данных, поэтому их невозможно различить.

Example: Taking N=10 and r=1, an equivalent set of values can be like { 1, 11, 21, 31, 41, 51, 61, 71, 81, 91. . . . . . . c_nx + 1 }, which all would be allocated to same location.

• Mash-функция: Mash-функция названа так, потому что это хеш-функция величины, что означает, что она вычисляет величины для сопоставления значений набора данных.
  Для числа cx + r , где c — величина, а x — основание (обычно принимается 10), c вычисляется с использованием оператора div ( X div N ) в мешанине вместо оператора mod, который используется в хеш-функции. . Но опять же значения не полностью отличаются друг от друга с помощью одной только функции затирания, и несколько значений сопоставляются с определенным местоположением.

Example: Taking N=10, c=5, we get the following set: { 50, 51, 52, 53, 54, 55, 56, 57, 58, 59 }. This set contains all the values of the cx + r where c  is constant for all values (c=5) and r is variable. That’s why for a single value of c we get multiple values mapping to the same slot.

Теперь, чтобы решить эту проблему, мы используем хэш-функции и функции мешанины вместе, чтобы получить уникальную порядковую пару (c, r) , где c — величина, полученная с помощью оператора div в функции месива , а r — остаточное значение, полученное модом оператор в хеш-функции .

Построение суперхэш-функции:
Рассмотрим диапазон значений [i, j], где i — нижняя граница, а j — верхняя граница диапазона. В настоящее время,

1. Вычислить длину диапазона,
   L = (j – i) + 1.
2. Определите ближайшее целое квадратное число (θ) к L с помощью:
   θ = потолок ( √ L )
3. Теперь значения порядковых пар можно рассчитать, используя:
   значение (dx, mx) = dxθ + mx

Пример:

Consider the range of values in the interval [ 20, 144 ], applying the steps of construction of the super-hash function:

1. Calculating the value of L ⇒ (144 – 20) + 1 = 125 
2. Calculating nearest square value to L ⇒  θ = ceil( √L ) = ceil( √125 ) = 12
3. Now for mapping, we also subtract the lower bound (here 20), so that all the values are mapped in the range 0. . . .(j – i).
   The resultant super-hash function: F(x)  =  { d = (x –  20) div 12  ,  m = (x – 20) mod 12 }
4. From the above super-hash function, we can find that for x = 20, we get the ordinal pair (0, 0) and for x = 144, we get (10, 4).

Сортировка по хешу на месте :

In-situ означает «на месте», названный из-за функционирования этого варианта на месте. При хеш-сортировке на месте суперхеш-функция итеративно используется для значений данных для сортировки данных. Но перед этим происходит этап инициализации, на котором исходное значение берется и используется суперхэш-функцией для сопоставления его с другим местоположением, где исходное значение заменяется значением, присутствующим в этом целевом местоположении, и, следовательно, создается новое значение. исходное значение (после замены). Этот процесс продолжает повторяться до тех пор, пока все данные не будут отсортированы или пока не будет достигнут конец списка данных.

Псевдокод алгоритма:

(v1, v2, v3, . . . . . .vn) <– initialize         // initialization for retrieving the source code
While Not(End of List) Do
    Temp <– get(v1, v2, v3. . . . vn);       // swapping of source and destination value
    Value –> put(v1, v2, v3. . . ..vn);
    Value = temp;
    (v1, v2, v3. . . . . .vn) –> super_Hash_Function(temp);      // using super-hash function to  retrieve the next source value
End of Loop                                                              

Следуйте приведенной ниже иллюстрации для лучшего понимания алгоритма:

Иллюстрация:

Let us consider a 2-dimensional 3 x 3 matrix with values ranging from 1-9 to illustrate the in-situ hash sort: 

Finding the range length, L  = (9 – 1) + 1 = 9 

Computing the nearest square integer to L = 9 ⇒ θ = ceil ( √9 ) = 3, Lower bound, i = 1
Therefore, the resultant super-hash function comes out to be: d = (x – 1) / 3, m = (x – 1) % 3
Let the initial matrix configuration be like this: 

m/d	0	1	2
0	5	8	1
1	9	7	2
2	4	6	3

• Starting initially at value(0, 0) = 5,  
  • Calculate the value of d and m for the value 5: d = (5- 1) div 3 = 1,  m = (5 -1 ) mod 3 = 1.
  • Hence, the new destination is at (1, 1) with value = 7.
  • Now, 5 and 7 will swap their respective positions. The resultant matrix will be: 

m/d	0	1	2
0	7	8	1
1	9	5	2
2	4	6	3

• Again using the (0, 0) position with value = 7. 
  • Find the values of d and m: d = (7 – 1) div 3 = 2,  m = (7 – 1) mod 3 = 0. 
  • Hence the obtained location is at (2, 0) where the value 4 is present. 
  • So, 4 and 7 will swap.

m/d	0	1	2
0	4	8	1
1	9	5	2
2	7	6	3

• On position (0, 0) value = 4. 
  • Calculating d and m for x = 4: d = (4 – 1) div 3 = 1, m = (4 – 1) mod 3 = 0.
  • The obtained position is (1, 0) with destination value = 9. 
  • Therefore, 9 and 4 will swap their positions. 

m/d	0	2	2
0	9	8	1
1	4	5	2
2	7	6	3

• Now, at position (0, 0), we have value = 9. 
  • So, d = (9 – 1) div 3 = 2,  m = (9 – 1) mod 3 = 2
  • The obtained position is (2, 2) with value  = 3. 
  • Therefore, 9 and 3 will swap their positions.

m/d	0	1	2
0	3	8	1
1	4	5	2
2	7	6	9

• At position (0, 0) value =  3.
  • Calculate d and m, d = (3 – 1) div 3 = 0, m = (3 – 1) mod 3 = 2.
  • Resultant position is (0, 2) with value = 1. 
  • Therefore, 1 and 3 will swap their positions.

m/d	0	1	2
0	1	8	3
1	4	5	2
2	7	6	9

• At position (0, 0), value = 1.
  • d = (1 – 1) div 3 = 0,  m = (1 – 1) mod 3 = 0.
  • The obtained position: (0, 0). This is the case of hysteresis, where the source value maps to its own location. This will cause an infinite loop as 1 on (0, 0) will keep on mapping position (0, 0) itself. 
  • So, to resolve this, we increment the position by 1 and get (0, 1) as our new source location. 
  • Now, computing the values of d and m for value = 8 at position (0, 1): d = (8 – 1) div 3 = 2, m  = (8 -1) mod 3 = 1. 
  • The new obtained location is (2, 1) with value = 6. 
  • Therefore, we swap the positions of 8 and 6.

m/d	0	1	2
0	1	6	3
1	4	5	2
2	7	8	9

• At position (0, 1) value = 6.
  • d = (6 – 1) div 3 = 1, m = (6 – 1) mod 3 = 2.
  • The new obtained location is at (1, 2) with value = 2. 
  • Therefore, 6 and 2 will swap their positions. The resultant matrix is:

m/d	0	1	2
0	1	2	3
1	4	5	6
2	7	8	9

The matrix is fully sorted now, so we stop our implementation here. 

Ниже приведен код для реализации хэш-сортировки In-Situ.

Анализ временной и пространственной сложности:

Временная сложность: O(N)

• Функции отображения хеш-сортировки имеют несколько возможных реализаций из-за расширяемой природы хэш-сортировки, поэтому мы можем взять константу c, где c >=1, обозначающую, что требуется хотя бы одно сопоставление.
• Теперь, поскольку супер-хеш-функция является составной функцией двух подфункций, общее время для сопоставлений будет вдвое больше числа суб-сопоставлений (обозначается с), поэтому мы умножаем с на 2, чтобы получить время, затрачиваемое для функции отображения для одного значения данных.
• Функция отображения будет применяться итеративно к каждому элементу данных, который в данном случае равен n, поэтому общая временная сложность получается: T(n) = 2.cN

Следовательно, T(N) = O(N)

Вспомогательное пространство: O(N)

Вспомогательное пространство зависит от используемого варианта хеш-сортировки.

• Для хеш-сортировки на месте сортировка происходит непосредственно в самой структуре данных.
• Следовательно, нам требуется (N + 1) пространство для реализации алгоритма in-situ, где N — количество элементов в структуре данных, а одно дополнительное пространство требуется для хранения временных значений при выполнении процесса подкачки.

Следовательно, S(N) = O(N)

Применение хэш-сортировки:

• Интеллектуальный анализ данных. Сортировка по хэшу может быть удобна для организации и поиска данных при интеллектуальном анализе данных, где имеются огромные объемы данных.
• Системы баз данных: для эффективного поиска данных.
• Операционные системы: Организация файлов.