Transposition Linear Search

Transposition Linear Search:

In this algorithm of searching, If the key is found then the key is swapped with the item at (keyIndex - 1) or the item before the search item.

The idea behind this algorithm is to move most search item/key to front/head of the array with each search. So that if the same item gets search again then it will take less time to search.

Below is the program for this algorithm of searching:

#include <iostream>

using namespace std;

/**
 * @brief swap: This function swaps the items.
 * @param pFirst: First item.
 * @param pSecond: Second item.
 */
void swap(int *pFirst, int *pSecond)
{
    int iTemp;

    iTemp = *pFirst;
    *pFirst = *pSecond;
    *pSecond = iTemp;
}

/**

 * @brief LinearSearch: This methods search the Key in the array passed in first param,

 *                      and if item/key is found then, swap it with the item at 1 less index.

 * @param objArr: object of Struct Array, Which contains array and Length of the array,

 *                in which we have to search the key.

 * @param iKey: Key needs to be search.

 * @return if key is found then retursns index of key otherwaise -1

 */

int transpostionLinearSearch(struct Array objArr, int iKey)
{
    int iKeyIndex = -1;

    for(int i = 0; i < objArr.iLength; ++i)
    {
        if (objArr.A[i] == iKey)
        {
            if (i == 0)
            {
                iKeyIndex = 0;
            }
            else
            {
                swap(objArr.A[i], objArr.A[i-1]);
                iKeyIndex = i - 1;
            }
            break;
        }
    }

    return iKeyIndex;
}

int main()

{

    Array objArr = {{2, 4, 6, 5, 7}, 5};

    int iIndex = TranspostionLinearSearch(objArr, 7);

    if (iIndex != -1)

        cout << "Element found at index: " << iIndex << endl;

    else

        cout << "Element not found." << endl;

}