查找使插入排序出现故障的哈希函数

Question

下面是插入排序的原始伪代码：

function INSERTIONSORT(A[0..n−1])
for i←1 to n−1 do 
    j←i−1 
    while j≥0 and A[j+1]<A[j] do 
          SWAP(A[j+1],A[j]) 
          j←j−1

一家公司在他们的一款产品中使用插入排序。您是该公司聘请的网络安全专家，负责评估其代码的任何安全漏洞。经过几次尝试，您成功地攻击了他们的插入排序代码并按以下方式对其进行了修改：

function INSERTIONSORT(A[0..n−1])
         for i←1 to n−1 do
         j←i−1 
         while j≥0 and HASH(A,j+1) < HASH(A,j) do 
               SWAP(A[j+1],A[j])
               j←j−1

换句话说，不是在“while”条件中将数组索引为 A[j] 和 A[j+1]，而是现在有一个将数组和索引作为参数的哈希函数，并且return 一个整数。你的工作是实现特定的哈希函数，这些函数将导致算法以不同的方式出现故障。

a) 实现一个哈希函数，使插入排序保持原数组不变。解释为什么你的解决方案有效。
b) 实现一个哈希函数，使插入排序在最坏的情况下总是运行复杂度，即使结果数组最终没有排序。解释为什么你的解决方案有效。
c) 实现一个散列函数，使插入排序对数组进行反向排序。解释为什么你的解决方案有效。

我认为 (a) 和 (b) 是 hash(A,j)=j 和 hash(A,j)=-j，但不知道这是否正确，也不知道 c.

Answer 1

**a）部分原始数组不变

#include <stdio.h>

int hash(int arr[], int i) {
    return i;
}

void insertionSort(int arr[], int n) {
    int i, j, temp;

    for (i = 1 ; i <= n - 1; i++)
    {
        j = i-1;
            while ( j >= 0 && hash(arr, j+1) < hash(arr, j))
            {           
                temp     = arr[j];
                arr[j]   = arr[j+1];
                arr[j+1] = temp;
                j--;
            }
    }
}

int main()
{
    int i;
    int arr[] = {5, 6, 7, 3, 2 , 9, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Original array unchanged:\n");
    for (i = 0; i <= n - 1; i++)
    {
        printf("%d\n", arr[i]);
    }
    return 0;
}

b) 部分最坏情况插入排序

#include <stdio.h>

int hash(int arr[], int i) {
    return -i;
}

void insertionSort(int arr[], int n) {
    int i, j, temp;

    for (i = 1 ; i <= n - 1; i++)
    {
        j = i-1;
            while ( j >= 0 && hash(arr, j+1) < hash(arr, j))
            {           
                temp     = arr[j];
                arr[j]   = arr[j+1];
                arr[j+1] = temp;
                j--;
            }
    }
}

int main()
{
    int i;
    int arr[] = {5, 6, 7, 3, 2 , 9, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    printf("In worst case(number of swaps maximum)\n");
    for (i = 0; i <= n - 1; i++)
    {
        printf("%d\n", arr[i]);
    }
    return 0;
}

c) 部分倒序排列。**

#include <stdio.h>

int hash(int arr[], int i) {
    return -arr[i];
}

void insertionSort(int arr[], int n) {
    int i, j, temp;

    for (i = 1 ; i <= n - 1; i++)
    {
        j = i-1;
            while ( j >= 0 && hash(arr, j+1) < hash(arr, j))
            {           
                temp     = arr[j];
                arr[j]   = arr[j+1];
                arr[j+1] = temp;
                j--;
            }
    }
}

int main()
{
    int i;
    int arr[] = {5, 6, 7, 3, 2 , 9, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted in reverse order:\n");
    for (i = 0; i <= n - 1; i++)
    {
        printf("%d\n", arr[i]);
    }
    return 0;
}

查找使插入排序出现故障的哈希函数

Find a hash function to malfunction insertion sort

algorithm

hash

insertion-sort